第一行 ：一个整数N ，表示方案和询问的总数。 接下来N行，每行开头一个单词“Query”或“Project”。 若单词为Query，则后接一个整数T，表示Blue Mary询问第T天的最大收益。 若单词为Project，则后接两个实数S，P，表示该种设计方案第一天的收益S，以及以后每天比上一天多出的收益P。

对于每一个Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，例如：该天最大收益为210或290时，均应该输出2）。

约定： 1 <= N <= 100000 1 <= T <=50000 0 < P < 100，| S | <= 10^6 提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

题解：同bzoj3165

#include
    
     #include
     
      #include
      
       #include
       
        #define N 500000#define P 500010#define MOD 1000000000#define eps 1e-10using namespace std;int t[P<<2],ansa,n,xx,kind,top,a[P],lastans;double b[P],ansb,x,y,x2,y2,p,q;char ch[10];struct use{   double k,b;   int l,r;   double f(int x){return k*x+b;}}line[N];int cross(use a,use b){  return floor((b.b-a.b)/(a.k-b.k));}use cal(double x,double y,double x2,double y2){   use ans;  ans.r=max(x,x2);ans.l=min(x,x2);  if (x2!=x) ans.k=(y2-y)/(x2-x),ans.b=y-ans.k*x;  else ans.k=0.0,ans.b=max(y,y2);  return ans;}int check(double x){  return (x>-eps)-(x
        
         0||(ff==0&&k
         
          0; int fr=check(line[x].f(r)-line[t[k]].f(r))>0; if (fl&&fr) t[k]=x; else if(fl||fr){ int mid=(l+r)>>1; int p=cross(line[x],line[t[k]]); if (p<=mid&&fl) insert(k<<1,l,mid,x); if (p<=mid&&fr) insert(k<<1,l,mid,t[k]),t[k]=x; if (p>mid&&fl) insert(k<<1|1,mid+1,r,t[k]),t[k]=x; if (p>mid&&fr) insert(k<<1|1,mid+1,r,x); } else up(x,l),up(x,r); } return; } int mid=(l+r)>>1; if (line[x].l<=mid) insert(k<<1,l,mid,x); if (line[x].r>mid) insert(k<<1|1,mid+1,r,x);}void query(int k,int l,int r,int x){ if (t[k]){ double tt=line[t[k]].f(x); int ff=check(tt-ansb); if ((ff>0||(ff==0&&ansa
          
           >1; if (x<=mid) query(k<<1,l,mid,x); else query(k<<1|1,mid+1,r,x); }int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%s",ch); if (ch[0]=='P'){ scanf("%lf%lf",&p,&q); x=1;y=p;x2=P;y2=y+(P-1)*q; line[++top]=cal(x,y,x2,y2); insert(1,1,P,top); } else{ scanf("%d",&xx);ansa=0;ansb=-1.0; query(1,1,P,xx); int ff=check(b[xx]-ansb); if ((ff>0||(ff==0&&a[xx]