题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1568
题意：两个操作：（1）添加一条直线y=kx+b；(1<=k<=100)（2）询问当前所有直线中x=t时y最大的y是多少？(1<=t<=50000)
思路：很明显，要把所有的直线维护成凸性，也就是对于任意一个x值，我们只保存y最大的那条直线。那么这个东西要能添加和删除。我们用set，set里按照斜率来建立。对于待插入的的一条直线我们首先找到与其斜率最近的两个，不妨令比其小的为pre，令比其大的为next，那么首先我们要判断要不要插入这条直线，设当前直线为cur,C(i,j)表示i与j的交点。首先我们看若cur与next的斜率相等的话，我们只需要根据其截距来判断要不要插入，若cur的截距小于等于next的截距则无需插入。接下来我们看斜率不等时。我们发现，若C(pre,cur)在next的下方，则无需插入；否则需要插入。那么一旦插入，我们就是要进行更新。比如，对于后继next以及后继的后继next1，若C(cur,next1)在next的上方，则需要将next删除。pre的删除类似。然后我们就能计算出cur在哪些区域上是最优的，[Xl,Xr]，然后将该区域上标记为cur最优，这个可以用线段树。
struct node
{
double k,b;
node(){}
node(double _k,double _b)
{
k=_k;
b=_b;
}
void get()
{
RD(b,k);
}
bool operator<(const node &b)const
{
return k<b.k;
}
};
node b[N];
struct Node
{
int L,R,x;
};
int n;
set<node> s;
#define type set<node>::iterator
Node a[N<<2];
void pushDown(int t)
{
if(a[t].L==a[t].R) return;
if(a[t].x)
{
a[t*2].x=a[t*2+1].x=a[t].x;
a[t].x=0;
}
}
void build(int t,int L,int R)
{
a[t].L=L;
a[t].R=R;
a[t].x=0;
if(L==R) return;
int mid=(L+R)>>1;
build(t*2,L,mid);
build(t*2+1,mid+1,R);
}
void update(int t,int L,int R,int x)
{
if(a[t].L==L&&a[t].R==R)
{
a[t].x=x;
return;
}
pushDown(t);
int mid=(a[t].L+a[t].R)>>1;
if(R<=mid) update(t*2,L,R,x);
else if(L>mid) update(t*2+1,L,R,x);
else
{
update(t*2,L,mid,x);
update(t*2+1,mid+1,R,x);
}
}
int get(int t,int pos)
{
if(a[t].x||a[t].L==a[t].R) return a[t].x;
pushDown(t);
int mid=(a[t].L+a[t].R)>>1;
if(pos<=mid) return get(t*2,pos);
else return get(t*2+1,pos);
}
double cal(node a,node b)
{
return (a.b-b.b)/(b.k-a.k);
}
void insert(node now)
{
now.b-=now.k;
type s2=s.lower_bound(now),s1=s2;
s1--;
node pre=*s1,sub=*s2;
double x;
if(now.k==sub.k)
{
if(now.b<=sub.b) return;
s.erase(s2);
s.insert(now);
}
else
{
x=(now.b-pre.b)/(pre.k-now.k);
if(sub.k*x+sub.b>now.k*x+now.b) return;
s.insert(now);
}
s2=s.find(now);s2--;
while(s2!=s.begin())
{
s1=s2; s1--;
pre=*s1,sub=*s2;
x=cal(now,pre);
if(sub.k*x+sub.b>now.k*x+now.b) break;
s.erase(s2);
s2=s.find(now);s2--;
}
s1=s.find(now);s1++; s2=s1;s2++;
while(s2!=s.end())
{
pre=*s1,sub=*s2;
x=cal(now,sub);
if(pre.k*x+pre.b>now.k*x+now.b) break;
s.erase(s1);
s1=s.find(now);s1++; s2=s1;s2++;
}
b[n]=now;
s1=s2=s.find(now);s1--;s2++;
pre=*s1;sub=*s2;
double x1=cal(now,pre),x2=cal(now,sub);
int L=(int)ceil(x1),R=(int)floor(x2);
if(L<1) L=1;
if(R>50000) R=50000;
if(L<=R) update(1,L,R,n);
}
int main()
{
s.insert(node(0,0));
s.insert(node(101,-INF));
build(1,1,50000);
int x,k;
char op[10];
node now;
RD(n);
while(n--)
{
RD(op);
if(op[0]=='P') now.get(),insert(now);
else
{
RD(x); k=get(1,x);
PR((int)(b[k].k*x+b[k].b)/100);
}
}
}