模板题：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; }