李超线段树模板入门
李超线段树模板入门
李超线段树用于解决如下问题：
-
要求在平面直角坐标系下维护两个操作（强制在线）：
-
在平面上加入一条线段。记第 i 条被插入的线段的标号为i，该线段的两个端点分别为
(x_0,y_0) ，(x_1,y_1) 。 -
给定一个数 k，询问与直线 x = k 相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出 0。
-
线段树上的每一个节点维护该节点所代表区间的最优线段
称一个区间的最优线段为完整覆盖该区间的所有线段中在该区间中点y值最大的那一条
修改
注意
李超线段树并不严格 对于一个可能在较多区间最优的线段 存储时它有可能只在它最优的最高的那个区间最优 这要求我们在更新时应该递归进入一条线段可能为最优的那个区间
对于一条线段 我们递归的修改
首先 对于一条线段的修改 仿照线段树区间修改
考虑
-
若该线段在中点处高于原有线段
将该区间最优设为该线段
- 该线段斜率大于原有线段
右半区间必然优于原有 左半区间需要递归进入继续修改
- 该线段斜率小于原有线段
左半区间必然大于原有线段 右半区间需要递归进入继续修改
-
若该线段中点处低于原有线段
维持原有线段为最优
- 该线段斜率大于原有线段
递归进入右区间继续修改
- 该线段斜率小于原有线段
递归进入左区间继续修改
查询
若查询一点 则找出包含该点的所有区间 比较这些区间中的最大值即可
代码
#include<bits/stdc++.h>
using namespace std;
#define mod1 39989
#define mod2 1000000000
#define N 500005
#define mid1 ((l+r)>>1)
#define mid ((tr[x].l+tr[x].r)>>1)
int n,xdcnt=0;
int tans[N];
struct XD
{
int x_0,y_0,x_1,y_1;
double k;
}xd[N];
struct nd
{
int l,r,cxd=0;
}tr[N<<4];
double zdy(int x,int k)
{
return xd[x].y_0+xd[x].k*(k-xd[x].x_0)*1.0;
}
void build(int x,int l,int r)
{
tr[x].l=l;
tr[x].r=r;
if(l==r)
return;
build(x<<1,l,mid1);
build(x<<1|1,mid1+1,r);
}
void insert(int x,int k)
{
if(xd[k].x_0<=tr[x].l&&tr[x].r<=xd[k].x_1)
{
if(tr[x].cxd==0)
{
tr[x].cxd=k;
return;
}
if(zdy(k,tr[x].l)<=zdy(tr[x].cxd,tr[x].l)&&zdy(k,tr[x].r)<=zdy(tr[x].cxd,tr[x].r))
return;
if(zdy(k,tr[x].l)>=zdy(tr[x].cxd,tr[x].l)&&zdy(k,tr[x].r)>=zdy(tr[x].cxd,tr[x].r))
{
tr[x].cxd=k;
return;
}
if(zdy(k,mid)>=zdy(tr[x].cxd,mid))
{
if(xd[k].k>xd[tr[x].cxd].k)
insert(x<<1,tr[x].cxd);
else
insert(x<<1|1,tr[x].cxd);
tr[x].cxd=k;
}
else
if(xd[k].k>xd[tr[x].cxd].k)
insert(x<<1|1,k);
else
insert(x<<1,k);
}
else
{
if(xd[k].x_0<=mid)
insert(x<<1,k);
if(xd[k].x_1>mid)
insert(x<<1|1,k);
}
}
int ask(int x,int k)
{
int lans;
if(tr[x].l==tr[x].r)
return tr[x].cxd;
if(k<=mid)
lans=ask(x<<1,k);
else
lans=ask(x<<1|1,k);
if(zdy(lans,k)>zdy(tr[x].cxd,k))
return lans;
else if(zdy(lans,k)==zdy(tr[x].cxd,k))
return max(tr[x].cxd,lans);
else
return tr[x].cxd;
}
int main()
{
//freopen("in.my","r",stdin);
//freopen("out.my","w",stdout);
int lastans=0;
scanf("%d",&n);
build(1,1,100000);
for(int i=1;i<=n;i++)
{
int op,x_0,x_1,y_0,y_1,x;
scanf("%d",&op);
if(op==0)
{
scanf("%d",&x);
x=(x+lastans-1+mod1)%mod1+1;
int ans;
ans=ask(1,x);
//if(zdy(ans,x)<max(xd[tans[x]].y_0,xd[tans[x]].y_1)||zdy(ans,x)==max(xd[tans[x]].y_0,xd[tans[x]].y_1)&&ans<tans[x])
//ans=tans[x];
printf("%d\n",ans);
lastans=ans;
}
if(op==1)
{
scanf("%d%d%d%d",&x_0,&y_0,&x_1,&y_1);
x_0=(x_0+lastans-1+mod1)%mod1+1;
x_1=(x_1+lastans-1+mod1)%mod1+1;
y_0=(y_0+lastans-1+mod2)%mod2+1;
y_1=(y_1+lastans-1+mod2)%mod2+1;
xd[++xdcnt].k=(y_1-y_0)*1.0/(x_1-x_0)*1.0;
if(x_0<=x_1)
{
xd[xdcnt].x_0=x_0;
xd[xdcnt].x_1=x_1;
xd[xdcnt].y_0=y_0;
xd[xdcnt].y_1=y_1;
}
else
{
xd[xdcnt].x_0=x_1;
xd[xdcnt].x_1=x_0;
xd[xdcnt].y_0=y_1;
xd[xdcnt].y_1=y_0;
}
if(x_0==x_1&&max(y_0,y_1)>max(xd[tans[x_0]].y_0,xd[tans[x_0]].y_1));
tans[x_0]=xdcnt;
if(x_0!=x_1)
insert(1,xdcnt);
}
}
return 0;
}