Segment 线段树
枫林晚
2018-05-11 16:54:39
## 题目大意：
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第 i 条被插入的线段的标号为 i
2.给定一个数 k,询问与直线 x = k 相交的线段中，交点最靠上的线段的编号。
**若有多条线段符合要求，输出编号最小的线段的编号**
（省略输入以及在线操作的要求）
## 分析：
明显的线段树特征：
1.有固定的 区间长度，（<=39989）
2.插入元素支持合并，（一个线段可以拆成两段线段）
所以我们用线段树来做这道题。
线段树维护什么元素开始不太好想。
发现要求一个交点最靠上的线段的编号，所以类似维护区间最大值，我们可以在每个区间内维护一个线段（这个线段两端坐标就是l和r，也就是说，恰好放在这个区间内），保证这个线段和x=mid这条竖直的线的交点的纵坐标是有史以来最大的。
我们在区间里记录下来这个线段的所属编号（注意不是线段编号，因为真实情况的一条线段可能会被劈成许多段，但是它们本质上还是同一个线段，在贡献答案的时候，还是要输出它们所代表的真实线段的编号的）。
同时用一个结构体记录下来每个线段的x1,x2,y1,y2以及所属编号hao。
注意由于要劈断，纵坐标不一定是整数，所以y1，y2都是double类型的。
```cpp
struct duan{
int x1,x2;
double y1,y2;
int hao;
}line[N*20];
struct node{
int id;
}t[4*(mod1+10)];
```
发现不需要build,pushup,pushdown,但是。。。
我们不能将区间原有线段因为中点处的值小了而“一
棒子打死”，它中点左边或者右边的值可能还会对答案产生贡献。
## 所以最关键的是add操作。
1.特判l==r
已经到了一个点上。
如果该点之前没有维护线段，直接维护现在的线段。
如果有，选择纵坐标靠上的直线（点），纵坐标相同，选择编号较小的。
2.如果没有恰好放在区间里。
如果不过mid，根据与mid关系左右查找。
如果过mid，劈两半分别查找。
3.如果找到了恰好的区间
如果该区间没有维护线段，维护该线段。
如果有，
①如果中点处新的优，留下新的，把旧的中，稍微大的一半留下（全劣则淘汰），下放到对应的子区间。
②如果中点处值相同。一般情况选择新的劈断的下放（省的建线段）。但是当新的编号较小，并且新的线段的右端点的纵坐标大于等于旧的，这时就要劈断旧的，将旧的右半部分下放。（使得mid处一定取得是新的线段，也就是编号较小的）
③如果中点处旧的优，同理。
查询的时候，直接沿着一条logn的路径查询，时刻更新最大值和ans即可。没有什么可多说的。
详见代码：（写的很丑，但是比较容易看懂）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod1=39989;
const int mod2=1e9;
int n;
int has;
int la;
int cntpool,cntdel;
int del[N];
struct duan{
int x1,x2;
double y1,y2;
int hao;
}line[N*20];
inline int newnode(int x1,int x2,double y1,double y2)
{
int r=cntdel?del[cntdel--]:++cntpool;
memset(line+r,0,sizeof (duan));
line[r].x1=x1,line[r].x2=x2,line[r].y1=y1,line[r].y2=y2;
return r;
}//取新节点
void dele(int x)
{
del[++cntdel]=x;
}//删除节点，回收空间
struct node{
int id;
}t[4*(mod1+10)];//树
double lv(int x1,int x2,double y1,double y2)
{
return (double)(y1-y2)/(1.0*x1-1.0*x2);
}//斜率
void add(int x,int l,int r,int x1,int x2,double y1,double y2,int hh)
{
if(l==r)
{
if(!t[x].id)
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
t[x].id=tt;
}
else{
double mx1=max(y1,y2);
double mx2=max(line[t[x].id].y1,line[t[x].id].y2);
if(mx1>mx2)
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
dele(t[x].id);
t[x].id=tt;
}
else if(mx1==mx2)
{
if(hh<line[t[x].id].hao)
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
dele(t[x].id);
t[x].id=tt;
}
}
}
return;
}//l==r情况
int mid=(l+r)>>1;
if(x1!=l||x2!=r)
{
if(x2<=mid) add(x<<1,l,mid,x1,x2,y1,y2,hh);
else if(x1>mid) add(x<<1|1,mid+1,r,x1,x2,y1,y2,hh);
else{
double k=lv(x1,x2,y1,y2);
double d=y1+((double)mid-x1)*k;
add(x<<1,l,mid,x1,mid,y1,d,hh);
add(x<<1|1,mid+1,r,mid+1,x2,d+k,y2,hh);
}
}//find
else{
if(!t[x].id)
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
t[x].id=tt;
}
else{
int p1=line[t[x].id].x1,p2=line[t[x].id].x2;
double q1=line[t[x].id].y1,q2=line[t[x].id].y2;
int oldh=line[t[x].id].hao;
double k1=lv(x1,x2,y1,y2);
double k2=lv(p1,p2,q1,q2);
double d1=y1+1.0*(mid-x1)*k1;//new d在中点的纵坐标
double d2=q1+1.0*(mid-p1)*k2;//old d
if(d1>d2)//new > old
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
dele(t[x].id);
t[x].id=tt;
if(q1<y1&&q2<y2) return;//warning!!
else if(q1>=y1)
{
add(x<<1,l,mid,p1,mid,q1,d2,oldh);
}
else if(q2>=y2)
{
add(x<<1|1,mid+1,r,mid+1,p2,d2+k2,q2,oldh);
}
}
else if(d1==d2)//new = old
{
if(q1<y1)
{
add(x<<1,l,mid,x1,mid,y1,d1,hh);
}
else if(q2<=y2)
{
if(hh<oldh)//move old
{
int tt=newnode(x1,x2,y1,y2);
line[tt].hao=hh;
dele(t[x].id);
t[x].id=tt;
add(x<<1,l,mid,p1,mid,q1,d2,oldh);
}
else{
add(x<<1|1,mid+1,r,mid+1,x2,d1+k1,y2,hh);
}
}
}
else if(d1<d2)//new < old
{
if(y1<q1&&y2<q2) return;//warning!!
else if(y1>=q1)
{
add(x<<1,l,mid,x1,mid,y1,d1,hh);
}
else if(y2>=q2)
{
add(x<<1|1,mid+1,r,mid+1,x2,d1+k1,y2,hh);
}
}
}
}//update
}
int ans;
double zui;
void query(int x,int l,int r,int to)
{
if(l==r) {
if(!t[x].id) return;//warning!!
double mx=max(line[t[x].id].y1,line[t[x].id].y2);
if(zui<mx)
{
zui=mx;
ans=line[t[x].id].hao;
}
else if(zui==mx)
{
if(ans>line[t[x].id].hao)
ans=line[t[x].id].hao;
}
return;
}
if(!t[x].id)
{
int mid=(l+r)>>1;
if(to<=mid) query(x<<1,l,mid,to);
else query(x<<1|1,mid+1,r,to);
}
else{
int x1=line[t[x].id].x1,x2=line[t[x].id].x2;
double y1=line[t[x].id].y1,y2=line[t[x].id].y2;
if(x1<=to&&to<=x2)
{
double k1=lv(x1,x2,y1,y2);
double d1=y1+((double)to-x1)*k1;
if(d1>zui)
{
zui=d1;
ans=line[t[x].id].hao;
}
else if(zui==d1)
{
if(ans>line[t[x].id].hao)
ans=line[t[x].id].hao;
}
}
int mid=(l+r)>>1;
if(to<=mid) query(x<<1,l,mid,to);
else query(x<<1|1,mid+1,r,to);
}
}
int main()
{
scanf("%d",&n);
int q,a,b,c,d;
for(int i=1;i<=n;i++)
{
scanf("%d",&q);
if(q&1)
{
has++;
scanf("%d%d%d%d",&a,&b,&c,&d);
a=(a+la-1)%mod1+1;
b=(b+la-1)%mod2+1;
c=(c+la-1)%mod1+1;
d=(d+la-1)%mod2+1;
if(a>c) swap(a,c),swap(b,d);
add(1,1,mod1+2,a,c,b,d,has);
}
else{
scanf("%d",&a);
zui=0.0,ans=0;
a=(a+la-1)%mod1+1;
query(1,1,mod1+2,a);
printf("%d\n",ans);
la=ans;
}
}
return 0;
}
```