bzoj千题计划219：bzoj1568: [JSOI2008]Blue Mary开公司

#include<cstdio>#include<iostream>#include<algorithm>using namespace std;#define N 100001double a[N<<2],b[N<<2];bool have[N<<2];long long ans;void read(int &x){ ???x=0; char c=getchar(); ???while(!isdigit(c)) c=getchar(); ???while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); } }void change(int k,int l,int r,double A,double B){ ???if(!have[k]) ???{ ???????have[k]=true; ???????a[k]=A; ???????b[k]=B; ???????return; ???} ???if(l==r) ???{ ???????a[k]=max(a[k],A); ???????return; ???} ???else ???{ ???????if(A>a[k]+(r-l)*b[k]) ???????{ ???????????a[k]=A; ???????????b[k]=B; ???????????return; ???????} ???????if(a[k]>A+(r-l)*B) return; ???????int mid=l+r>>1; ???????if(A<a[k]) ???????{ ????????????if(A+(mid-l)*B>a[k]+(mid-l)*b[k]) ???????????{ ???????????????change(k<<1,l,mid,a[k],b[k]); ???????????????a[k]=A; ???????????????b[k]=B; ???????????} ???????????else change(k<<1|1,mid+1,r,A+(mid+1-l)*B,B); ???????} ???????else ???????{ ???????????if(A+(mid-l)*B>a[k]+(mid-l)*b[k]) ???????????{ ???????????????change(k<<1|1,mid+1,r,a[k]+(mid+1-l)*b[k],b[k]); ???????????????a[k]=A; ???????????????b[k]=B; ???????????} ???????????else change(k<<1,l,mid,A,B); ???????} ???????}}void query(int k,int l,int r,int p){ ???if(!have[k]) return; ???if(l==r) ???{ ???????ans=max(ans,(long long)a[k]); ???????return; ???} ???ans=max(ans,(long long)(a[k]+(p-l)*b[k])); ???int mid=l+r>>1; ???if(p<=mid) query(k<<1,l,mid,p); ???else query(k<<1|1,mid+1,r,p);}int main(){ ???int n,x; ???char c[8]; ???double s,p; ???read(n); ???while(n--) ???{ ????????scanf("%s",c); ????????if(c[0]==‘Q‘) ????????{ ????????????read(x); ????????????ans=0; ????????????query(1,1,N-1,x); ????????????cout<<ans/100<<‘\n‘; ????????} ????????else ????????{ ????????????scanf("%lf%lf",&s,&p); ????????????change(1,1,N-1,s,p); ????????} ???}}