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 39989using 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\n",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;
}
