李超线段树

问题：
洛谷P4097
在平面直角坐标系维护两个操作：
1.加入一条线段。
2.求目前平面直角坐标系中截一条直线\(x=k\)中与线段交点\(y\)最大的是那一条线段。
解决：
李超线段树模板。
首先建一个以\(x\)为区间的线段树。
和普通线段树的主要区别是在对懒标记的处理上，这里是是没有单独的下方标记操作的，当到达一段被覆盖区间时，如果新标记的左右端点的\(y\)值均大于旧标记的，则更新标记，返回，均小于就直接返回，一大一小就找两线段的交点，交点靠近的一端\(y\)值大的线段下放交点所在的那半边，剩余的那条留下做新标记。
修改复杂度是\(\Theta (\log_2^2 n)\)
代码:

#include<iostream>
using namespace std;
int kd(){
	int x=0,f=1;
	char a=getchar();
	while(a<'0'||a>'9'){
		if(a=='-'){
			f=-1;
		}
		a=getchar();
	}
	while(a>='0'&&a<='9'){
		x=x*10+a-'0';
		a=getchar();
	}
	return x*f;
}
int n;
struct node{
	int l,r;
	double lzl;
	double lzr;
	int id;
}tree[159956];
void build(int i,int l,int r){
	tree[i].l=l;
	tree[i].r=r;
	tree[i].lzl=0;
	tree[i].lzr=0;
	tree[i].id=0;
	if(l==r){
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}
void add(int i,int l,int r,double x,double y,int p){
	if(tree[i].l==l&&tree[i].r==r){
		if(x==tree[i].lzl&&y==tree[i].lzr){
			tree[i].id=min(tree[i].id,p);
			return ;
		}
		if(x>tree[i].lzl&&y>tree[i].lzr){
			tree[i].lzl=x;
			tree[i].lzr=y;
			tree[i].id=p;
			return ;
		}
		if(x<tree[i].lzl&&y<tree[i].lzr){
			return ;
		}
		if(x>=tree[i].lzl){
			if(x-tree[i].lzl<=tree[i].lzr-y){
				add(i*2,tree[i*2].l,tree[i*2].r,x,x+(y-x)*1.0/(r-l)*(tree[i*2].r-tree[i*2].l),p);
			}
			else{
				swap(tree[i].lzl,x);
				swap(tree[i].lzr,y);
				swap(tree[i].id,p);
				add(i*2+1,tree[i*2+1].l,tree[i*2+1].r,y+(x-y)*1.0/(r-l)*(tree[i*2+1].r-tree[i*2+1].l),y,p);
			}
		}
		else{
			if(y-tree[i].lzr<tree[i].lzl-x){
				add(i*2+1,tree[i*2+1].l,tree[i*2+1].r,y+(x-y)*1.0/(r-l)*(tree[i*2+1].r-tree[i*2+1].l),y,p);
			}
			else{
				swap(tree[i].lzl,x);
				swap(tree[i].lzr,y);
				swap(tree[i].id,p);
				add(i*2,tree[i*2].l,tree[i*2].r,x,x+(y-x)*1.0/(r-l)*(tree[i*2].r-tree[i*2].l),p);
			}
		}
		return ;
	}
	if(tree[i*2].r>=r){
		add(i*2,l,r,x,y,p);
		return ;
	}
	if(tree[i*2+1].l<=l){
		add(i*2+1,l,r,x,y,p);
		return ;
	}
	add(i*2,l,tree[i*2].r,x,x+(y-x)*1.0/(r-l)*(tree[i*2].r-l),p);
	add(i*2+1,tree[i*2+1].l,r,y+(x-y)*1.0/(r-l)*(r-tree[i*2+1].l),y,p);
}
struct nod{
	double maxn;
	int id;
}ans;
void search(int i,int p){
	if(tree[i].l==tree[i].r){
		double x=tree[i].lzl;
		if(x>ans.maxn||(x==ans.maxn&&tree[i].id<ans.id)){
			ans.maxn=x;
			ans.id=tree[i].id;
		}
		return ;
	}
	double x=tree[i].lzl+(tree[i].lzr-tree[i].lzl)*1.0/(tree[i].r-tree[i].l)*(p-tree[i].l);
	if(x>ans.maxn||(x==ans.maxn&&tree[i].id<ans.id)){
		ans.maxn=x;
		ans.id=tree[i].id;
	}
	if(tree[i*2].r>=p){
		search(i*2,p);
	}
	else{
		search(i*2+1,p);
	}
}
int lastans=0;
int main(){
	cin>>n;
	build(1,1,39989);
	int cnt=0;
	while(n--){
		int opt;
		opt=kd();
		if(opt==1){
			cnt++;
			int x_1,x_2;
			int y_1,y_2;
			x_1=kd();y_1=kd();x_2=kd();y_2=kd();
			x_1=(x_1+lastans-1)%39989+1;
			y_1=(y_1+lastans-1)%1000000000+1;
			x_2=(x_2+lastans-1)%39989+1;
			y_2=(y_2+lastans-1)%1000000000+1;
			if(x_1==x_2){
				y_1=max(y_1,y_2);
				y_2=max(y_1,y_2);
			}
			if(x_1>x_2){
				swap(x_1,x_2);
				swap(y_1,y_2);
			}
			add(1,x_1,x_2,y_1,y_2,cnt);
		}
		if(opt==0){
			int k=kd();
			k=(k+lastans-1)%39989+1;
			ans.maxn=0;
			ans.id=0;
			search(1,k);
			printf("%d\n",ans.id);
			lastans=ans.id;
		}
	}
	return 0;
}