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
Sample Output
0
0
0
0
0
写这个题目，我们需要用到线段树的标记永久化。那么什么是线段树的标记永久化呢？
所谓标记永久化，是指线段树的标记不会下传，那么我每次询问的时候把叶子到根的路径上的信息处理下就好了。
不会下传的标记？那有什么用？
用处其实非常多，例如常数小，或者说有些题目在标记下传的时候无法维护信息，这样可以用标记永久化。
那么这题呢？的确是标记永久化，不过不绝对。
首先本题的方案都可以看做是一条直线，那么这题便转化成了插入n条直线，然后询问某x位置的最大的y。
每次加入一条直线时，首先判断该直线与区间所记录的直线（记录在Mid）的斜率大小，然后判断在Mid点时，哪条直线的答案更优
如果是斜率大的答案更优，那么在(Mid,r]内，一定是斜率大的答案优，因此我们只需要将斜率小的直线下放到左儿子，并且将当前区间记录的直线更新为斜率大的直线；如果是斜率小的答案更优，那么在[l,Mid]内一定是斜率小的更优，所以我们就将斜率大的直线传到右儿子中递归更新，当前区间同样更新
其实读到这里应该还会有个小问题，由于线段树上记录的是一段段的折线，并且这些折线斜率必定递增。我们在上文所说的某条直线在更新了区间记录的答案后，就把另一条直线往一边下放了，难道另一边不用下放吗？又或者说，当前记录的新直线，不用在另一边下放，判断一下，更新一下吗？
标记永久化带来的这个疑问，必然有解决的方法。我们统计答案的时候，将路过的所有直线都计算一下，更新答案，就不会有什么问题了。
又或者我们换个思想，每个区间所记录的直线，只是保证Mid最优的直线，那么我们的问题也就解决了
#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define inf 0x7f7f7f7fusing namespace std;typedef long long ll;typedef unsigned int ui;typedef unsigned long long ull;inline int read(){ ???int x=0,f=1;char ch=getchar(); ???for (;ch<‘0‘||ch>‘9‘;ch=getchar()) ?if (ch==‘-‘) ???f=-1; ???for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) ???x=(x<<1)+(x<<3)+ch-‘0‘; ???return x*f;}inline void print(int x){ ???if (x>=10) ????print(x/10); ???putchar(x%10+‘0‘);}const int N=1e5,Day=5e4;double K[N+10],B[N+10]; ?//K是斜率,B是与y轴交点（来自初中数学的摧残）int Lazy[N*4+10]; ?//标记记录的不是斜率，是序号char s[10];#define ls (p<<1)#define rs (p<<1|1)bool check(int x,int y,int cnt){return K[x]*(cnt-1)+B[x]>K[y]*(cnt-1)+B[y];}//位于cnt点的两直线判断void change(int p,int l,int r,int t){ ???if (l==r){ ???????if (check(t,Lazy[p],l)) Lazy[p]=t; ???????return; ???} ???int mid=(l+r)>>1; ???if (K[t]>K[Lazy[p]]){//将判断对照前面的文字说明便十分明了 ???????if (check(t,Lazy[p],mid)) ??change(ls,l,mid,Lazy[p]),Lazy[p]=t; ???????else ???change(rs,mid+1,r,t); ???} ???if (K[t]<K[Lazy[p]]){ ???????if (check(t,Lazy[p],mid)) ??change(rs,mid+1,r,Lazy[p]),Lazy[p]=t; ???????else ???change(ls,l,mid,t); ???}}double get(int x,int cnt){return K[x]*(cnt-1)+B[x];}//得到cnt点的答案double query(int p,int l,int r,int t){ ???if (l==r) ??return get(Lazy[p],t); ???int mid=(l+r)>>1; ???double ans=get(Lazy[p],t); ?//一路更新答案 ???if (t<=mid) ans=max(ans,query(ls,l,mid,t)); ???if (t>mid) ?ans=max(ans,query(rs,mid+1,r,t)); ???return ans;}int main(){ ???int n=read(),cnt=0; ???for (int i=1;i<=n;i++){ ???????scanf("%s",s+1); ???????if (s[1]==‘P‘){ ???????????cnt++; ???????????scanf("%lf%lf",&B[cnt],&K[cnt]); ???????????change(1,1,Day,cnt); ?//题目并未告诉你明确的天数，因此只能这么玩 ???????} ???????if (s[1]==‘Q‘){ ???????????int x=read(); ???????????double t=query(1,1,Day,x); ???????????printf("%d\n",(int)t/100); ?//按题目要求输出 ???????} ???} ???return 0;}