传送门
题意简述：维护整体加一条线段，求单点极值。
思路：
直接上李超线段树维护即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
typedef double db;
const int N=1e5+5;
const db eps=1e-7;
struct Line{db k,b;}a[N];
inline bool check(const int&x,const int&y,const int&l){
db t1=a[x].k*l+a[x].b,t2=a[y].k*l+a[y].b;
return t1<t2;
}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
int id[N<<2];
inline void update(int p,int l,int r,int k){
if(!id[p])id[p]=k;
int l1=id[p],l2=k;
if(check(l1,l2,l))swap(l1,l2);
id[p]=l1;
if(l==r||fabs(a[l1].k-a[l2].k)<eps)return;
db x=(a[l1].b-a[l2].b)/(a[l2].k-a[l1].k);
if(x<l||x>r)return;
if(x<=mid)return id[p]=l2,update(lc,l,mid,l1);
return update(rc,mid+1,r,l2);
}
inline int query(int p,int l,int r,int k){
int val=id[p]?(int)(a[id[p]].k*k+a[id[p]].b)/100:0;
if(l==r)return val;
return max(val,k<=mid?query(lc,l,mid,k):query(rc,mid+1,r,k));
}
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
char s[8];
for(ri x,tot=0,n=read(),tt=1;tt<=n;++tt){
scanf("%s",s);
if(s[0]=='Q')cout<<SGT::query(1,1,n,read())<<'\n';
else{
double x,y;
scanf("%lf%lf",&x,&y);
a[++tot]=(Line){y,x-y};
SGT::update(1,1,n,tot);
}
}
return 0;
}