C118【模板】李超线段树 P4254 [JSOI2008] Blue Mary 开公司

视频链接：

 

 

 

Luogu P4254 [JSOI2008] Blue Mary 开公司

// 李超线段树 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;#define N 50005
#define ls u<<1
#define rs u<<1|1
int n,cnt;
struct line{double k,b; //斜率,截距
}p[N*2];
int tr[N*4]; //线段编号double Y(int id,int x){ //求Y值return p[id].k*x+p[id].b;
}
void change(int u,int l,int r,int L,int R,int id){ //区修int mid=(l+r)>>1;if(L<=l&&r<=R){if(Y(id,mid)>Y(tr[u],mid)) swap(id,tr[u]);if(Y(id,l)>Y(tr[u],l)) change(ls,l,mid,L,R,id);if(Y(id,r)>Y(tr[u],r)) change(rs,mid+1,r,L,R,id);return;}if(L<=mid) change(ls,l,mid,L,R,id);if(mid<R) change(rs,mid+1,r,L,R,id);
}
double query(int u,int l,int r,int x){ //点查if(l==r) return Y(tr[u],x);int mid=(l+r)>>1;double t=Y(tr[u],x);if(x<=mid) return max(t,query(ls,l,mid,x));else return max(t,query(rs,mid+1,r,x));
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){char op[10]; scanf("%s",op);if(op[0]=='P'){double b,k; scanf("%lf%lf",&b,&k);p[++cnt]={k,b-k};change(1,1,N,1,N,cnt);}else{int x; scanf("%d",&x);printf("%d\n",(int)query(1,1,N,x)/100);}}
}