首页 > 代码库 > BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
1568: [JSOI2008]Blue Mary开公司
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1080 Solved: 379
[Submit][Status][Discuss]
Description
Input
第一行 ：一个整数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
提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。
Output
对于每一个Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，
例如：该天最大收益为210或290时，均应该输出2）。没有方案时回答询问要输出0
Sample Input
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
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
Sample Output
0
0
0
0
0
0
0
0
0
HINT
Source
超哥线段树的模板题。
超哥线段树是处理一次函数的一种线段树，
在超哥线段树中，每一个节点保存着一个一次函数所对应的编号，
那他是怎么保存的呢？
借用一位大神的图片
没错就是这样，
然后对于每一次插入操作，
我们去递归当前 值小的节点 的值 可能比 值大的节点 的 值 大的方向。。。。。。。
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<bitset>#define ls k<<1#define rs k<<1|1using 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;}
BZOJ 1568: [JSOI2008]Blue Mary开公司(超哥线段树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。