1568: [JSOI2008]Blue Mary開公司【李超線段樹】
又是一道闆子題，不過要注意的是，如果目前為負數的話輸出0。
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;
struct Seg{double K,B;bool id;double f(int x){return K*x+B;}};
struct LC_Tree{
Seg Tre[MAXN<<2];bool vis[MAXN<<2];
void PushDown(int rt,int L,int R,Seg Now){
if(!vis[rt]) return (void)(Tre[rt]=Now,vis[rt]=1);
double L1=Now.f(L),R1=Now.f(R),L2=Tre[rt].f(L),R2=Tre[rt].f(R);
if(L1<=L2&&R1<=R2) return;
if(L1>=L2&&R1>=R2) return (void)(Tre[rt]=Now);
double pos=(Now.B-Tre[rt].B)/(Tre[rt].K-Now.K);
int mid=(R+L)>>1;
if(pos<=mid) PushDown(rt<<1,L,mid,L1>L2?Now:Tre[rt]);
else PushDown(rt<<1|1,mid+1,R,R1>R2?Now:Tre[rt]);
if((L1>L2&&pos>=mid)||(R1>R2&&pos<mid)) Tre[rt]=Now;
}
double _abs(double x){return x<0?-x:x;}
Seg Query(int rt,int L,int R,int p){
if(L==R) return vis[rt]?Tre[rt]:(Seg){0,0,0};
int mid=(R+L)>>1;Seg Ans=(Seg){0,0,0};
if(p<=mid) Ans=Query(rt<<1,L,mid,p);
else Ans=Query(rt<<1|1,mid+1,R,p);
if(!vis[rt]) return Ans;
double p1=Ans.f(p),p2=Tre[rt].f(p);
if(!Ans.id||p1<p2) return Tre[rt];else return Ans;
}
}T;
int n;
int main(){
scanf("%d",&n);char ch[10];
while(n--){
scanf("%s",ch);
if(ch[0]=='P'){
double K,B;scanf("%lf%lf",&B,&K);
T.PushDown(1,1,50000,(Seg){K,B-K,n+1});
}else{
int x;scanf("%d",&x);
Seg A=T.Query(1,1,50000,x);
printf("%d\n",max(0,int(A.f(x)/100)));
}
}
return 0;
}