【李超线段树】BZOJ1568[JSOI2008]Blue Mary开公司

前言：

这道题是李超线段树的一道模板题，鉴于李超线段树（似乎）应用性并不广，所以就用这道题顺便写写总结。

题目大意：

题目很鬼畜，一句话题意是：
动态插入一些离散的直线（有斜率），同时询问每条直线在某个点的取值的最大值。

算法介绍

差不多李超线段树就是干这个用的了

我们用一个标记来表示一个区间的最优线段，每次插入一个线段时，设原来的最优线段为$l_1$，插入的线段为$l_2$
首先比较两条线段的斜率大小，并且求出其分别在区间中点的值，
如果斜率较大的直线$l_{max}$在中点的取值比$l_{min}$小，那么$l_{max}$在左半部分一定被$l_{min}$或其他的线完全覆盖，所以只能向右区间转移。
如果$l_{max}$在中点的取值比$l_{min}$大，那么$l_{min}$在右半部分也一定被完全覆盖。只能向左区间转移。

最后求答案时，只需要将：线段树上覆盖了该节点的所有区间，分别求其最优线段在该点的取值，取最大值即可。
代码相当好写

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 50010
using namespace std;
double a[MAXN],b[MAXN],ans;
int n,q,tr[MAXN*4];
bool pushup(int x,int y,int now){--now;return a[x]+b[x]*now>a[y]+b[y]*now;
}
void update(int now,int l,int r,int id){if(l==r){if(pushup(now,tr[id],l))tr[id]=now;return;}int mid=(l+r)>>1;if(b[now]>b[tr[id]]){if(pushup(now,tr[id],mid)){update(tr[id],l,mid,id*2);tr[id]=now;}elseupdate(now,mid+1,r,id*2+1);}else{if(pushup(now,tr[id],mid)){update(tr[id],mid+1,r,id*2+1);tr[id]=now;}elseupdate(now,l,mid,id*2);}
}
void query(int q,int l,int r,int id){ans=max(ans,a[tr[id]]+b[tr[id]]*(q-1));if(l==r)return ;int mid=(l+r)>>1;if(q<=mid)query(q,l,mid,id*2);elsequery(q,mid+1,r,id*2+1);
}
char s[20];
int cnt,x;
int main(){SF("%d",&q);for(int i=1;i<=q;i++){SF("%s",s);if(s[0]=='P'){cnt++;SF("%lf%lf",&a[cnt],&b[cnt]);update(cnt,1,MAXN-10,1);}else{SF("%d",&x);ans=0;query(x,1,MAXN-10,1);PF("%d\n",(int)ans/100);}}
}
?