III.李超线段树
李超线段树是一种可以维护动态凸包的线段树。更准确地说，其可以支持的常规操作有两种：
-
在平面直角坐标系中插入一条线段。
-
询问在坐标系中的一个点 \((x,+\infty)\) 向下看，能看到的点的坐标。换句话说，是一条自无穷高处引下的垂线与所有线段的交点中最高的那个点。
其具体实现如下：
我们以 \(x\) 坐标为下标，建一棵线段树（可能需要离散化）。然后，在线段树的每个区间上，我们维护所有完整地包含该区间的线段中，在该区间的中点处最高的那条。具体而言，当我们插入一条线段时，首先要把它在线段树上拆作众多小区间。当递归到某个完整的区间时，考虑将其与该区间上本来记录的中点处最高线段做比较。明显，共有三种可能：
- 新插入的线段严格不低于原本线段。此时直接替换就行。
- 新插入的线段严格不高于原本线段。此时直接不替换就行。
- 新插入的线段与原本线段有交。此时，先在当前区间中记录中点更高的那条，然后明显，在其一个子区间内，更高的一定是当前区间中记录的线段，可以不管；而在其另一个子区间中，更高的就不一定是它了，此时要递归入该子区间继续修改。
下面考虑分析复杂度。显然，如果插入的全部是直线，复杂度为 \(n\log n\)，因为两个子区间中最多访问其中一个；而如果我们插入的全是线段，因为要先拆到各个子区间上，所以复杂度就为 \(n\log^2n\)。
然后询问时就仿照标记永久化，直接在一路上的区间处用大区间上记录的线段更新即可。明显是 \(O(n\log n)\) 的。
III.I.[JSOI2008]Blue Mary开公司
是板题，甚至插入的都不是线段而是直线，就更好处理了。
真的很好写。
代码：
#include<bits/stdc++.h>
using namespace std;
const int lim=50000;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{double lv,rv;}seg[200100];
double calc(double lv,double rv,int l,int r,int P){return lv+(rv-lv)/(r-l)*(P-l);}
void modify(int x,int l,int r,double LV,double RV){
if(LV+RV>seg[x].lv+seg[x].rv)swap(seg[x].lv,LV),swap(seg[x].rv,RV);
if(l==r)return;
if(LV>seg[x].lv)modify(lson,l,mid,LV,calc(LV,RV,l,r,mid));
if(RV>seg[x].rv)modify(rson,mid+1,r,calc(LV,RV,l,r,mid+1),RV);
}
double query(int x,int l,int r,int P){
if(l>P||r<P)return 0;
double ret=calc(seg[x].lv,seg[x].rv,l,r,P);
if(l!=r)ret=max(ret,query(lson,l,mid,P)),ret=max(ret,query(rson,mid+1,r,P));
return ret;
}
char s[10];
int T;
int main(){
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%s",s);
if(s[0]=='Q'){int x;scanf("%d",&x);printf("%d\n",(int)(query(1,1,lim,x)/100));}
else{double l,r;scanf("%lf%lf",&l,&r),r=l+(lim-1)*r;modify(1,1,lim,l,r);}
}
return 0;
}