bzoj 1568. [JSOI2008]Blue Mary开公司

题目大意

支持两种操作

• 插入一条线段

• 询问一个位置最上面的点

1568. [JSOI2008]Blue Mary开公司

solve

这是一道李超线段树的模板

对于李超线段树就可以维护线段的最值问题

在修改一个点的时候

1. 若当前区间还没有记录最优势线段，则记录最优势线段并返回。

2. 若当前区间的最优势线段被插入的线段完全覆盖，则把最优势线段修改为被插入线段并返回。

3. 若当前区间的最优势线段把被插入线断完全覆盖，则直接返回。

4. 若当前区间最优势线段与被插入线段有交，则先判断哪条线段在当前区间更优，并把更劣的线段下传到交点所在子区间。（交点两边的部分被这两条线段分别控制，而我们已经让在中点更优的那条线段作为区间最优势线段，因此更劣的那条线段只有可能在交点所在子区间超过当前区间的最优势线段）

code

#include<bits/stdc++.h>
typedef long long LL;
const LL TT=1e9+7;
const double eps=1e-12;
const int maxn=5e4+5;
using namespace std;
struct line{
	double k,b;
	int l,r;
}sgt[maxn<<2];
int N;
char op[10];
inline double calc(line a,int pos){return a.k*pos+a.b;}
inline int cross(line a,line b){return floor((a.b-b.b)/(b.k-a.k));}
void build(int now,int l,int r){
	sgt[now].k=sgt[now].b=0;sgt[now].l=1;sgt[now].r=50000;
	if(l==r)return ;
	int mid=(r-l>>1)+l;
	build(now<<1,l,mid);build(now<<1|1,mid+1,r);
}
void modify(int now,int l,int r,line k){
	if(k.l<=l&&r<=k.r){
		if(calc(k,l)-calc(sgt[now],l)>eps&&calc(k,r)-calc(sgt[now],r)>eps) sgt[now]=k;
		else if(calc(k,l)-calc(sgt[now],l)>eps||calc(k,r)-calc(sgt[now],r)>eps){
			int mid=(r-l>>1)+l;
			if(calc(k,mid)-calc(sgt[now],mid)>eps){
				line tmp=k;k=sgt[now];sgt[now]=tmp;
			}
			if(cross(k,sgt[now])-mid<-eps) modify(now<<1,l,mid,k);
			else modify(now<<1|1,mid+1,r,k);
		}
	}
	else {
		int mid=(r-l>>1)+l;
		if(k.l<=mid)modify(now<<1,l,mid,k);
		if(mid<k.r)modify(now<<1|1,mid+1,r,k);
	}
}
double query(int now,int l,int r,int x){
	if(l==r)return calc(sgt[now],x);
	else {
		int mid=(r-l>>1)+l;
		double ans=calc(sgt[now],x);
		if(x<=mid) return max(ans,query(now<<1,l,mid,x));
		else return max(ans,query(now<<1|1,mid+1,r,x));
	}
}
int main(){
	freopen("1568.in","r",stdin);
	freopen("1568.out","w",stdout);
	scanf("%d",&N);
	build(1,1,50000);
	for(int i=1;i<=N;i++){
		scanf("%s",op);
		if(op[0]=='P'){
			double s,p;
			scanf("%lf%lf",&s,&p);
			line now;now.l=1;now.r=50000;now.k=p;now.b=s-p;
			modify(1,1,50000,now);
		}
		else {
			int x;scanf("%d",&x);
			int ret=floor(query(1,1,50000,x));
			printf("%d
",ret/100);
		}
	}
	return 0;
}