模板题：BZOJ ： 1568: [JSOI2008]Blue Mary开公司
给定若干条直线，求在x=x0处（x0为正整数）y的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#define ll long long
#define llu unsigned ll
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=50050;
const int n=50000;
struct node
{
    double k,b;
    int l,r,flag;
}t[maxn<<2];

double cross(double k1,double b1,double k2,double b2)
{
    return (b2-b1)/(k1-k2);
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].k=t[cnt].b=0;
    t[cnt].flag=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,cnt<<1);
    build(mid+1,r,cnt<<1|1);
}

void change(double k,double b,int cnt)
{
    if(!t[cnt].flag)
    {
        t[cnt].k=k,t[cnt].b=b;
        t[cnt].flag=1;
        return ;
    }
    //如果能l==r的话，在这一点y值一定可比较，而不会向下更新。
    double y1=k*t[cnt].l+b,y2=k*t[cnt].r+b;
    double y3=t[cnt].k*t[cnt].l+t[cnt].b,y4=t[cnt].k*t[cnt].r+t[cnt].b;
    if(y1<=y3&&y2<=y4) return ;
    if(y1>=y3&&y2>=y4)
    {
        t[cnt].k=k,t[cnt].b=b;
        return ;
    }
    double posx=cross(k,b,t[cnt].k,t[cnt].b);
    if(posx<=t[cnt<<1].r)
    {
        if(y1>=y3) change(k,b,cnt<<1);
        else
        {
            change(t[cnt].k,t[cnt].b,cnt<<1);
            t[cnt].k=k,t[cnt].b=b;
        }
    }
    else
    {
        if(y1>=y3)
        {
            change(t[cnt].k,t[cnt].b,cnt<<1|1);
            t[cnt].k=k,t[cnt].b=b;
        }
        else change(k,b,cnt<<1|1);
    }
}

double ans;
void ask(int pos,int cnt)
{
    if(t[cnt].flag) ans=max(ans,t[cnt].k*pos+t[cnt].b);
    if(t[cnt].l==t[cnt].r) return ;
    if(pos<=t[cnt<<1].r) ask(pos,cnt<<1);
    else ask(pos,cnt<<1|1);
}

int main(void)
{
   char op[20];
   int p,x;
   double k,b;
   build(1,n,1);
   scanf("%d",&p);
   for(int i=1;i<=p;i++)
   {
       scanf("%s",op);
       if(op[0]=='P')
       {
           scanf("%lf%lf",&b,&k);
           change(k,b-k,1);
       }
       else
       {
           scanf("%d",&x);
           ans=0;
           ask(x,1);
           printf("%lld\n",(ll)(ans/100));
       }
   }
   return 0;
}