问题：
洛谷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;
}