[JSOI2008]Blue Mary开公司
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1808 Solved: 639
[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
题解：可以看出许多条一次函数，然后每次询问的时候就是求一个x的坐标的答
案，超哥线段树可以说就是永久标记维护各段的最大值。
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 ?9 #define N 5000710 #define ls p<<111 #define rs p<<1|112 using namespace std;13 inline int read()14 {15 ????int x=0,f=1;char ch=getchar();16 ????while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}17 ????while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();}18 ????return x*f;19 }20 21 int n,tot;22 double ans;23 int tr[N<<2];24 char ch[20];25 struct Node26 {27 ????double k,b;28 }a[N<<1];29 30 bool judge(int x,int y,int t)31 {32 ????t--;33 ????return a[x].b+a[x].k*t>a[y].b+a[y].k*t;34 }35 void ins(int p,int l,int r,int x)36 {37 ????if (l==r)38 ????{39 ????????if (judge(x,tr[p],l)) tr[p]=x;40 ????????return;41 ????}42 ????int mid=(l+r)>>1;43 ????if (a[x].k>a[tr[p]].k)44 ????{45 ????????if (judge(x,tr[p],mid)) ins(ls,l,mid,tr[p]),tr[p]=x;46 ????????else ins(rs,mid+1,r,x);47 ????}48 ????else49 ????{50 ????????if (judge(x,tr[p],mid)) ins(rs,mid+1,r,tr[p]),tr[p]=x;51 ????????else ins(ls,l,mid,x);52 ????}53 }54 void query(int p,int l,int r,int x)55 {56 ????ans=max(ans,a[tr[p]].k*(x-1)+a[tr[p]].b);57 ????if (l==r) return;58 ????int mid=(l+r)>>1;59 ????if (x<=mid) query(ls,l,mid,x);60 ????else query(rs,mid+1,r,x);61 }62 int main()63 {64 ????n=read();65 ????for (int i=1;i<=n;i++)66 ????{67 ????????scanf("%s",ch);68 ????????if (ch[0]==‘P‘)69 ????????{70 ????????????tot++;71 ????????????scanf("%lf%lf",&a[tot].b,&a[tot].k);72 ????????????ins(1,1,n,tot);73 ????????}74 ????????else75 ????????{76 ????????????ans=0;query(1,1,n,read());77 ????????????printf("%d\n",(int)ans/100);78 ????????}79 ????}80 }bzoj 1568 [JSOI2008]Blue Mary开公司 超哥线段树
原文地址：https://www.cnblogs.com/fengzhiyuan/p/8847520.html