bzoj 1568: [JSOI2008]Blue Mary开公司

.

题意：有n个操作，每个操作可以是插入一条直线或询问某个点最高的位置。
题解：线段树
线段树维护l~r之间可能作为答案的最低的直线（有点绕，还是上图吧）

红色那条就是这个节点记录的。加入新直线时，只用在它可以完全覆盖原来记录的那条时才替换；假如它被原来的直线完全覆盖了，就可以直接return，不用再往下更新。查找就一路伸到底取最大就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,num=0;
const double eps=1e-13;
struct seg
{
    double k,b;
};
struct tree
{
    int l,r,lc,rc;
    seg c;
}tr[100010];
bool tf=0;

int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
    }
    return i;
}
double cal(int x,seg y)
{
    return y.k*x+y.b;
}
void ins(int i,seg c)
{
    if(cal(tr[i].l,tr[i].c)-cal(tr[i].l,c)<=eps&&cal(tr[i].r,tr[i].c)-cal(tr[i].r,c)<=eps)
    {
        tr[i].c=c;
        return;
    }
    if(cal(tr[i].l,tr[i].c)-cal(tr[i].l,c)>eps&&cal(tr[i].r,tr[i].c)-cal(tr[i].r,c)>eps||tr[i].l==tr[i].r)
    return;
    ins(tr[i].lc,c);
    ins(tr[i].rc,c);
}
double get(int i,int x)
{
    if(tr[i].l==tr[i].r)
    return cal(x,tr[i].c);
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(x<=md)
    return max(cal(x,tr[i].c),get(lc,x));
    else
    return max(cal(x,tr[i].c),get(rc,x));
}
int main()
{
    scanf("%d",&n);
    bt(1,50000);
    for(int i=0;i<n;i++)
    {
        char s[9];
        scanf("%s",s);
        if(s[0]=='P')
        {
            tf=1;
            double k,b;
            scanf("%lf%lf",&b,&k);
            ins(1,(seg){k,b-k});
        }
        else
        {
            int x;
            scanf("%d",&x);
            if(!tf)
            puts("0");
            else
            printf("%d\n",int(get(1,x)/100));
        }
    }
}