P4097 [HEOI2013]Segment
题目描述
要求在平面直角坐标系下维护两个操作：
- 在平面上加入一条线段。记第 \(i\) 条被插入的线段的标号为 \(i\)
- 给定一个数 \(k\),询问与直线 \(x = k\) 相交的线段中，交点最靠上的线段的编号。
输入输出格式
输入格式：
第一行一个整数 \(n\)，表示共 \(n\) 个操作
接下来 \(n\) 行，每行第一个数为 \(0\) 或 \(1\)
若该数为 \(0\)，则后面跟着一个正整数 \(k\)，表示询问与直线 \(x = ((k + lastans – 1)\%39989+1)\)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中\(\%\)表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段 \(y\) 坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号
若该数为 \(1\)，则后面跟着四个正整数 \(x_0, y_0, x_1, y_1\)，表示插入一条两个端点为 \(((x_0+lastans-1)\%39989+1\),\((y_0+lastans-1)%10^9+1)\)和 \(((x_1+lastans-1)%39989+1,(y1+lastans-1)\%10^9+1)\) 的线段
其中 \(lastans\) 为上一次询问的答案。初始时 \(lastans=0\)
输出格式：
对于每个 \(0\) 操作，输出一行，包含一个正整数，表示交点最靠上的线段的编 号。若不存在与直线相交的线段，答案为 \(0\)
说明
对于\(30\%\)的数据，\(n ≤ 1000\)
对于\(100\%\)的数据，\(1 ≤ n ≤ 10^5, 1 ≤ k, x_0, x_1 ≤ 39989, 1 ≤ y_0 ≤ y_1 ≤ 10^9\)
李超线段树
对\(x\)建线段树，每个区间存一个线段进行标记永久化。
这个线段用斜截式子\(k,b\)保存
当查询时，遍历的时候拿所有的节点进行更新。
当修改时，当完全覆盖当前区间时
如果这个区间还没有线段，占上去
如果这个区间上的线段和当前线段在此段无交点，选择上面的一个保留
-
判断交点在\(mid\)左边还是右边
-
以在左边为例
如果当前左端点>区间左端点，当前区间保留，自己进左儿子去更新
否则把自己留着这，把当前区间的踹下去
右边同理
-
因为每个线段最多被划分成\(\log n\)段，所以复杂度是\(O(n\log^2 n)\)的
Code:
#include <cstdio>
#include <algorithm>
#include <cmath>
using std::max;
const int N=1e5+10;
int n=39989,m;
struct seg
{
double k,b;
int id;
seg(){}
seg(int x,int y,int xx,int yy,int Id)
{
k=1.0*(yy-y)/(1.0*(xx-x));
b=y-k*x;
id=Id;
}
double pos(double x){return k*x+b;}
}mx[N<<2];
const double eps=1e-5;
bool dcmp(double x,double y){return fabs(x-y)<eps;}
struct beecute
{
int id;double mx;
beecute(){}
beecute(int Id,double Mx){id=Id,mx=Mx;}
bool friend operator <(beecute a,beecute b){return dcmp(a.mx,b.mx)?a.id>b.id:a.mx<b.mx;}
}bee[N],las;
#define ls id<<1
#define rs id<<1|1
void change(int id,int L,int R,int l,int r,seg ins)
{
int Mid=L+R>>1;
if(l==L&&r==R)
{
if(!mx[id].id) {mx[id]=ins;return;}
double a=ins.pos(1.0*l),b=ins.pos(1.0*r),c=mx[id].pos(1.0*l),d=mx[id].pos(1.0*r);
if(a>c&&b>d) {mx[id]=ins;return;}
if(a<c&&b<d) return;
double x=(mx[id].b-ins.b)/(ins.k-mx[id].k);
if((double)(Mid)<x)
{
if(a>c)
{
change(rs,Mid+1,R,Mid+1,r,mx[id]);
mx[id]=ins;
}
else change(rs,Mid+1,R,Mid+1,r,ins);
}
else
{
if(a>c) change(ls,L,Mid,l,Mid,ins);
else
{
change(ls,L,Mid,l,Mid,mx[id]);
mx[id]=ins;
}
}
return;
}
if(r<=Mid) change(ls,L,Mid,l,r,ins);
else if(l>Mid) change(rs,Mid+1,R,l,r,ins);
else change(ls,L,Mid,l,Mid,ins),change(rs,Mid+1,R,Mid+1,r,ins);
}
void query(int id,int l,int r,int p,beecute &ret)
{
if(mx[id].id) ret=max(ret,beecute(mx[id].id,mx[id].pos(1.0*p)));
if(l==r) return;
int mid=l+r>>1;
if(p<=mid) query(ls,l,mid,p,ret);
else query(rs,mid+1,r,p,ret);
}
int main()
{
scanf("%d",&m);
for(int id=0,op,k,a,b,c,d,i=1;i<=m;i++)
{
scanf("%d",&op);
if(op)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
a=(a+las.id-1)%n+1,b=(b+las.id-1)%(int)(1e9)+1;
c=(c+las.id-1)%n+1,d=(d+las.id-1)%(int)(1e9)+1;
if(a>c) std::swap(a,c),std::swap(b,d);
if(a==c) bee[a]=max(bee[a],beecute(++id,1.0*max(b,d)));
else change(1,1,n,a,c,seg(a,b,c,d,++id));
}
else
{
scanf("%d",&k);
k=(k+las.id-1)%n+1;
las=bee[k];
query(1,1,n,k,las);
printf("%d\n",las.id);
}
}
return 0;
}
2019.2.14