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), (x1), (y1)，表示插入一条两个端点为 (((x0+lastans-1) \% 39989+1), ((y0+lastans-1) \%10^9+1)) 和 (((x1+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
对于 (30\%) 的数据，(n leq 1000)
对于 (100\%) 的数据，(1 leq n leq 10^5, 1 leq k, x0, x1 leq 39989, 1 leq y0 , y1 leq 10^9)
题解
李超线段树模板题。
推荐一篇好的 (blog) : https://blog.csdn.net/flere825/article/details/76283734
很巧妙的思想。
关键点就是引入区间“最优势线段” & 动态维护它，保证对每一个位置，答案一定在包含这个位置的区间的“最优势线段”中。
代码
注意坑点！！！！！
(y) 的模数为 (10^9)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-9
#define P 39989
using namespace std;
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x;
}
const int N = 100005;
typedef double db;
int tot;
db K[N],B[N];
struct node{
node *ch[2];
int id;
}pool[P*2],*root;
int cnt;
void build(node *p,int l,int r){
p->id=0;
if(l==r) return;
int mid=(l+r)>>1;
build(p->ch[0]=&pool[++cnt],l,mid);
build(p->ch[1]=&pool[++cnt],mid+1,r);
}
inline db cal(int x,int c) { return K[x]*c+B[x]; }
bool better(int x,int y,int c){
if(x==0) return false;
if(y==0) return true;
db cx=cal(x,c),cy=cal(y,c);
if(fabs(cx-cy)<eps) return x<y;
return cx>cy;
}
void insert(node *p,int l,int r,int L,int R,int c){
if(l==L && r==R){
int mid=(l+r)>>1;
if(better(c,p->id,mid)) swap(p->id,c);
int tl=better(p->id,c,l),tr=better(p->id,c,r);
if(!c || l==r || (tl && tr)) return;
if(tl) insert(p->ch[1],mid+1,r,mid+1,r,c);
else insert(p->ch[0],l,mid,l,mid,c);
return;
}
int mid=(l+r)>>1;
if(R<=mid) insert(p->ch[0],l,mid,L,R,c);
else if(L>mid) insert(p->ch[1],mid+1,r,L,R,c);
else {
insert(p->ch[0],l,mid,L,mid,c);
insert(p->ch[1],mid+1,r,mid+1,R,c);
}
}
int ans;
void query(node *p,int l,int r,int c){
ans = better(p->id,ans,c) ? p->id : ans ;
if(l==r) return;
int mid=(l+r)>>1;
if(c<=mid) query(p->ch[0],l,mid,c);
else query(p->ch[1],mid+1,r,c);
}
int main()
{
int n,opt,lastans=0,k,x0,y0,x1,y1;
n=read();
root=&pool[++cnt];
build(root,1,P);
while(n--){
opt=read();
if(opt==0){
k=(read()+lastans-1)%P+1;
ans=0;
query(root,1,P,k);
lastans=ans;
printf("%d
",lastans);
}
else{
x0=(read()+lastans-1)%P+1; y0=(read()+lastans-1)%1000000000+1;
x1=(read()+lastans-1)%P+1; y1=(read()+lastans-1)%1000000000+1;
if(x0>x1) swap(x0,x1),swap(y0,y1);
tot++;
K[tot]=1.0*(y1-y0)/(x1-x0);
B[tot]=y0-K[tot]*x0;
insert(root,1,P,x0,x1,tot);
}
}
return 0;
}