超哥线段树
#include<cstdio>
#include<algorithm>
using namespace std;
const int lim=50000;
double ans;
char s[15];
struct node{
double k,b;
}Line[2000005];
inline double check(node a,node b){
return (a.b-b.b)/(b.k-a.k);
}
inline double calc(double x,node line){
return line.k*x+line.b;
}
inline void update(int t,node line){
Line[t]=line;
}
inline void insert(int t,int l,int r,int x,int y,node line){
if (l>y || r<x) return;
if (l>=x && r<=y){
double Lmax=calc(l,line),Rmax=calc(r,line);
double Lt=calc(l,Line[t]),Rt=calc(r,Line[t]);
if (Lmax<=Lt && Rmax<=Rt) return;
else if (Lmax>Lt && Rmax>Rt) update(t,line);
else{
int mid=(l+r)>>1;
double Key=check(line,Line[t]);
node To=line;
if (Key<=mid) {
if (Lmax<Lt) {
To=Line[t];
update(t,line);
}
insert(t<<1,l,mid,x,y,To);
}
else {
if (Rmax<Rt){
To=Line[t];
update(t,line);
}
insert(t<<1|1,mid+1,r,x,y,To);
}
}
return;
}
int mid=(l+r)>>1;
insert(t<<1,l,mid,x,y,line);
insert(t<<1|1,mid+1,r,x,y,line);
}
void query(int t,int l,int r,int key){
double Key=calc(key,Line[t]);
if (Key>ans) ans=Key;
if (l==r) return;
int mid=(l+r)>>1;
if (key<=mid) query(t<<1,l,mid,key);
else query(t<<1|1,mid+1,r,key);
}
int main(){
int q;
scanf("%d",&q);
while (q--){
scanf("%s",s);
if (s[0]=='Q'){
int X;
scanf("%d",&X);
ans=0;
query(1,1,lim,X);
printf("%d\n",(int)(ans/100));
}
else{
double B,K;
scanf("%lf%lf",&B,&K);
B-=K;
insert(1,1,lim,1,lim,(node){K,B});
}
}
return 0;
}