[HEOI2013] Segment李超线段树

RT
感觉会模板就差不多了，可用作处理一些线段或直线的问题，转化过来的也可以。比如DP的斜率优化，直线的话只用一个log,线段要两个log。
[HEOI2013] Segment

• 模板

#include<iostream>
using namespace std;
const int mod1=39989;
const int mod2=1e9;
const double esp=1e-9;
const int N=1e5;
typedef pair<double,int> pi;
int n,s[N<<2],cnt;
struct line{
	double k,b;
}li[N];
int cmp(double x,double y){
	if(x-y>esp)	return 1;
	if(y-x>esp)	return -1;
	return 0;	
}
double calc(int id,int d){
	return li[id].k*d+li[id].b;
}
void add(int xi,int yi,int xj,int yj){
	cnt++;
	if(xi==xj)
		li[cnt].b=max(yi,yj),li[cnt].k=0;
	else
		li[cnt].k=1.0*(yj-yi)/(xj-xi),li[cnt].b=yi-li[cnt].k*xi;
}
void upd(int p,int cl,int cr,int u){
	int &v=s[p],mid=cl+cr>>1;
	if(cmp(calc(u,mid),calc(v,mid))==1)	swap(u,v);
	int l=cmp(calc(u,cl),calc(v,cl)),r=cmp(calc(u,cr),calc(v,cr));
	if(l==1||(!l&&u<v))	upd(p<<1,cl,mid,u);
	if(r==1||(!r&&u<v))	upd(p<<1|1,mid+1,cr,u);
}
void update(int l,int r,int u,int p=1,int cl=1,int cr=mod1){
	if(l<=cl&&cr<=r){
		upd(p,cl,cr,u);
		return;
	}
	int mid=cl+cr>>1;
	if(l<=mid)	update(l,r,u,p<<1,cl,mid);
	if(mid<r)	update(l,r,u,p<<1|1,mid+1,cr);
}
pi pmax(pi x,pi y){
	if(cmp(x.first,y.first)==1)	return x;
	if(cmp(x.first,y.first)==-1)	return y;
	return x.second<y.second?x:y;
}
pi query(int d,int p=1,int cl=1,int cr=mod1){
	if(cl>d||cr<d)	return {0,0};
	double res=calc(s[p],d),mid=cl+cr>>1;
	if(cl==cr)	return {res,s[p]};
	return pmax({res,s[p]},pmax(query(d,p<<1,cl,mid),query(d,p<<1|1,mid+1,cr)));
}
int main(){
	int xi,xj,yi,yj,d,op,laas=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%d%d",&xi,&yi,&xj,&yj);
			xi=(xi+laas-1+mod1)%mod1+1; 
			xj=(xj+laas-1+mod1)%mod1+1; 
			yi=(yi+laas-1+mod2)%mod2+1; 
			yj=(yj+laas-1+mod2)%mod2+1;
			if(xi>xj)	swap(xi,xj),swap(yi,yj);
			add(xi,yi,xj,yj);
			update(xi,xj,cnt);
		}
		else{
			scanf("%d",&d);
			d=(d+laas-1+mod1)%mod1+1;
			laas=query(d).second;
			printf("%d\n",laas);
		}
	}
}