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