第一行 :一个整数N ,表示方案和询问的总数。
接下来N行,每行开头一个单词“Query”或“Project”。
若单词为Query,则后接一个整数T,表示Blue Mary询问第T天的最大收益。
若单词为Project,则后接两个实数S,P,表示该种设计方案第一天的收益S,以及以后每天比上一天多出的收益P。
1 <= N <= 100000 1 <= T <=50000 0 < P < 100,| S | <= 10^6
提示:本题读写数据量可能相当巨大,请选手注意选择高效的文件读写方式。
对于每一个Query,输出一个整数,表示询问的答案,并精确到整百元(以百元为单位,
例如:该天最大收益为210或290时,均应该输出2)。没有方案时回答询问要输出0
10 Project 5.10200 0.65000 Project 2.76200 1.43000 Query 4 Query 2 Project 3.80200 1.17000 Query 2 Query 3 Query 1 Project 4.58200 0.91000 Project 5.36200 0.39000
0 0 0 0 0
超哥线段树的模板题。
超哥线段树是处理一次函数的一种线段树,
在超哥线段树中,每一个节点保存着一个一次函数所对应的编号,
那他是怎么保存的呢?
借用一位大神的图片
没错就是这样,
然后对于每一次插入操作,
我们去递归当前 值小的节点 的值 可能比 值大的节点 的 值 大的方向。。。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int MAXN=1000001;
inline void read(int &n)
{
char c='+';int x=0;bool flag=0;
while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
n=flag==1?-x:x;
}
struct funtion
{
double k,b;
}a[MAXN];// 记录每一条线段
int tree[MAXN];// 每一个节点所对应线段的编号
int tot=0;// 总的线段数量
inline int pd(int now,int will,int day)
{
--day;
return a[now].k*day+a[now].b>a[will].k*day+a[will].b;
}
inline void insert(int k,int l,int r,int now)
{
if(l==r)
{
if(pd(now,tree[k],l)) tree[k]=now;
return ;
}
int mid=(l+r)>>1;
if(a[now].k>a[tree[k]].k)// 当前点的斜率比目标点的斜率大
{
if(pd(now,tree[k],mid)) insert(ls,l,mid,tree[k]),tree[k]=now;
else insert(rs,mid+1,r,now);
}
else
{
if(pd(now,tree[k],mid)) insert(rs,mid+1,r,tree[k]),tree[k]=now;
else insert(ls,l,mid,now);
}
}
double ans=0;
void query(int k,int l,int r,int now)
{
ans=max(ans,a[tree[k]].k*(now-1)+a[tree[k]].b);
if(l==r) return ;
int mid=(l+r)>>1;
if(now<=mid) query(ls,l,mid,now);
else query(rs,mid+1,r,now);
}
int main()
{
ios::sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
string opt;
cin>>opt;
if(opt[0]=='P')
{
++tot;
cin>>a[tot].b>>a[tot].k;
insert(1,1,n,tot);
}
else if(opt[0]=='Q')
{
int p;
cin>>p;
ans=0;
query(1,1,n,p);
printf("%d\n",(int)(ans/100));
}
}
return 0;
}