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
李超线段树模板题
http://www.yhzq-blog.cc/%e6%9d%8e%e8%b6%85%e7%ba%bf%e6%ae%b5%e6%a0%91%e6%80%bb%e7%bb%93/
http://blog.csdn.net/clover_hxy/article/details/52503987
https://wenku.baidu.com/view/6735b8e29b89680203d825b7.html
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 struct Line 8 { 9 ??double b,k;10 }line,tree[400001];11 char s[11];12 double ans;13 int n,N=50000;14 int i;15 bool pd(Line a,Line b,double x)16 {17 ??return (a.k*(x-1)+a.b>b.k*(x-1)+b.b);18 }19 double cal(Line a,double x)20 {21 ??return a.k*(x-1)+a.b;22 }23 void update(int rt,int l,int r,Line x)24 {25 ??if (l==r)26 ????{27 ??????if (pd(x,tree[rt],l))28 ????tree[rt]=x;29 ??????return;30 ????}31 ??int mid=(l+r)/2;32 ??if (x.k>tree[rt].k)33 ????{34 ??????if (pd(x,tree[rt],mid)) update(rt<<1,l,mid,tree[rt]),tree[rt]=x;35 ??????else update(rt<<1|1,mid+1,r,x);36 ????}37 ??if (x.k<tree[rt].k)38 ????{39 ??????if (pd(x,tree[rt],mid)) update(rt<<1|1,mid+1,r,tree[rt]),tree[rt]=x;40 ??????else update(rt<<1,l,mid,x);41 ????}42 }43 double query(int rt,int l,int r,int x)44 {45 ??if (l==r)46 ????{47 ??????return cal(tree[rt],l);48 ????}49 ??int mid=(l+r)/2;50 ??ans=max(ans,cal(tree[rt],x));51 ??if (x<=mid) ans=max(ans,query(rt<<1,l,mid,x));52 ??else ans=max(ans,query(rt<<1|1,mid+1,r,x));53 ??return ans;54 }55 int main()56 {int T;57 ??cin>>n;58 ??for (i=1;i<=n;i++)59 ????{60 ??????scanf("%s",s);61 ??????if (s[0]==‘P‘)62 ????{63 ??????scanf("%lf%lf",&line.b,&line.k);64 ??????update(1,1,N,line);65 ????}66 ??????else67 ????{68 ??????scanf("%d",&T);69 ??????ans=0;70 ??????ans=query(1,1,N,T);71 ??????printf("%d\n",(int)ans/100);72 ????}73 ????}74 }[JSOI2008]Blue Mary开公司
原文地址：https://www.cnblogs.com/Y-E-T-I/p/8318962.html