Description
要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
Input
第一行一个整数n，表示共n 个操作。
接下来n行，每行第一个数为0或1。
若该数为 0，则后面跟着一个正整数 k，表示询问与直线
x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为 1，则后面跟着四个正整数 x0, y0, x 1, y 1，表示插入一条两个端点为
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x
1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。
Output
对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。
Sample Input
6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5
Sample Output
2
0 3
HINT
对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。
分析：
终于要学习新的数据结构了
灰常的兴奋啊~~
新知识的学习从抄板子开始
从零开始的数据结构学习。。。
丁队的板子。。。看不懂
只能上网找资源orz
李超线段树板子
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const double eps=1e-10;
const int swt=1000000000;
const int N=100010;
const int mod=39989;
struct nd{
int x,y,ff;
};
nd tree[N<<2];
struct node{
int x,y;
double k,b;
double f(int x){
return k*x+b;
}
};
node li[N]; //线段
int lastans,tot=0,ansi,wi[N];
double ansy,wy[N]; //ansy记录最大坐标，ansi记录线段编号
int dcmp(double x)
{
if (fabs(x)<eps) return 0;
else if (x>0) return 1;
else return -1;
}
int cross(int u,int w) //交点
{
return floor((li[w].b-li[u].b)/(li[u].k-li[w].k));
}
node getline(int x,int y,int xx,int yy)
{
node ans;
ans.x=min(x,xx); //定义域
ans.y=max(x,xx);
if (ans.x!=ans.y){
ans.k=(double)(yy-y)/(double)(xx-x);
ans.b=y-x*ans.k; //kx+b=y
}
else ans.k=0.0,ans.b=max(y,yy); //一条竖线
return ans;
}
void update(int u,int x) //x=u和线段的交点
{
double y=li[x].f(u);
int p=dcmp(y-wy[u]);
if (!wi[u]||(p>0||(p==0&&x<wi[u])))
{
wy[u]=y; //维护端点值
wi[u]=x;
}
}
void build(int bh,int l,int r)
{
tree[bh].x=l;
tree[bh].y=r;
tree[bh].ff=0;
if (l==r) return;
int mid=(l+r)>>1;
build(bh<<1,l,mid); build(bh<<1|1,mid+1,r);
}
void insert(int bh,int u) //把每个线段分成logn个区间
{
if (li[u].x<=tree[bh].x&&li[u].y>=tree[bh].y) //线段树节点完全包含线段
{
if (!tree[bh].ff){
tree[bh].ff=u;return; ///没被覆盖过
}
int mid=(tree[bh].x+tree[bh].y)>>1;
int ll=dcmp(li[u].f(tree[bh].x)-li[tree[bh].ff].f(tree[bh].x));
int rr=dcmp(li[u].f(tree[bh].y)-li[tree[bh].ff].f(tree[bh].y));
//通过f函数计算线段树节点的左右端点与两条线段的交点
if (ll>0&&rr>0) //完全覆盖
tree[bh].ff=u;
else if (ll>0||rr>0) //李超线段树的精髓啊
{
int tt=cross(tree[bh].ff,u);
if (tt<=mid&&ll>0) insert(bh<<1,u);
if (tt<=mid&&rr>0) insert(bh<<1,u),tree[bh<<1|1].ff=u; //
if (tt>mid&&rr>0) insert(bh<<1|1,u);
if (tt>mid&&ll>0) insert(bh<<1|1,u),tree[bh<<1].ff=u; //
} else update(tree[bh].x,u),update(tree[bh].y,u);
return;
}
int mid=(tree[bh].x+tree[bh].y)>>1;
if (li[u].x<=mid) insert(bh<<1,u);
if (li[u].y>mid) insert(bh<<1|1,u);
}
void ask(int bh,int u)
{
if (tree[bh].ff)
{
double y=li[tree[bh].ff].f(u);
int s=dcmp(y-ansy);
if (s>0||(s==0&&ansi>tree[bh].ff))
ansy=y,ansi=tree[bh].ff;
}
if (tree[bh].x==tree[bh].y) return;
int mid=(tree[bh].x+tree[bh].y)>>1;
if (u<=mid) ask(bh<<1,u);
if (u>mid) ask(bh<<1|1,u);
}
int main()
{
int T;
scanf("%d",&T);
build(1,1,mod);
while (T--)
{
int opt,x,y,xx,yy;
scanf("%d",&opt);
if (opt==1)
{
scanf("%d%d%d%d",&x,&y,&xx,&yy);
x=(x+lastans-1)%mod+1;y=(y+lastans-1)%swt+1;
xx=(xx+lastans-1)%mod+1;yy=(yy+lastans-1)%swt+1;
li[++tot]=getline(x,y,xx,yy);
insert(1,tot);
}
else
{
scanf("%d",&x);
x=(x+lastans-1)%mod+1;
ansi=0;ansy=-1.0;
ask(1,x);
int s=dcmp(wy[x]-ansy);
if (s>0||(s==0&&wi[x]<ansi)) ansi=wi[x];
lastans=ansi;
printf("%d
",lastans);
}
}
}