题目链接

P4097 [HEOI2013]Segment

题目描述

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第 \(i\) 条被插入的线段的标号为 \(i\)。
2. 给定一个数 \(k\)，询问与直线 \(x = k\) 相交的线段中，交点纵坐标最大的线段的编号。

输入格式

本题输入强制在线。

输入的第一行是一个整数 \(n\)，代表操作的个数。

接下来 \(n\) 行，每行若干个用空格隔开的整数，第 \((i + 1)\) 行的第一个整数为 \(op\)，代表第 \(i\) 次操作的类型。

若 \(op = 0\)，则后跟一个整数 \(k\)，代表本次操作为查询所所有与直线 \(x = (k + lastans - 1) \bmod 39989 + 1\) 相交的线段中，交点纵坐标最大的线段编号。

若 \(op = 1\)，则后跟四个整数 \(x_0, y_0, x_1, y_1\)，记 \(x_i' = (x_i + lastans - 1) \bmod 39989 + 1\) ，\(y_i' = (y_i + lastans - 1) \bmod 10^9 + 1\)。本次操作为插入一条两端点分别为 \((x_0', y_0')\)，\((x_1',y_1')\) 的线段。

其中 \(lastans\) 为上次询问的答案，初始时，\(lastans = 0\)。

输出格式

对于每次查询，输出一行一个整数，代表交点纵坐标最大的线段的编号。若不存在任何一条线段与查询直线有交，则输出 \(0\)；若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段，同时 \(lastans\) 也应更新为编号最小的一条线段。

样例 #1

样例输入 #1

6 
1 8 5 10 8 
1 6 7 2 6 
0 2 
0 9 
1 4 7 6 7 
0 5

样例输出 #1

2 
0 
3

提示

样例输入输出 \(1\) 解释

对于第一次操作，解密后为 1 8 5 10 8。

对于第二次操作，解密后为 1 6 7 2 6。

对于第三次操作，解密后为 0 2，此时 \(lastans\) 被更新为 \(2\)。

对于第四次操作，解密后为 0 11，此时 \(lastans\) 被更新为 \(0\)。

对于第五次操作，解密后为 1 4 7 6 7。

对于第六次操作，解密后为 0 5。

数据范围与约定

对于 \(30\%\) 的数据，保证 \(n \leq 10^3\)。

对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq k, x_0, x_1 \leq 39989\)，\(1 \leq y_0, y_1 \leq 10^9\)。

提示

不保证 \(x_0 \neq x_1\)。对于一条 \(x_0' = x_1'\) 的线段，认为其与 \(x = x_0'\) 的交点为其两端点中纵坐标较大的端点。

解题思路

李超线段树

李超线段树的主要用途：插入线段，查询单点极值
用线段树维护 \(x\) 轴，每个区间节点 \([l,r]\) 保存 \(x\) 取 \(mid=\frac{l+r}{2}\) 的最优 \(y\) 的线段编号，对于一个新来的线段 \(line\)，设线段 \(line\) 的 \(x\) 范围为 \([l,r]\)，则该线段只会对被该区间包含的线段树节点区间有影响，即先找到被影响的线段树节点，如果当前线段树中没有保存编号，则直接将该节点作为整个线段树的初始最优编号，否则将线段 \(line\) 跟线段树中保存的线段 \(line'\) 进行比较，如果对于节点区间中心 \(mid\) 来说 \(line\) 要更优则当前线段树节点保存 \(line\) 这条线段，假设 \(line\) 要比 \(line'\) 更劣，如果对于节点区间左端点来说，新线段 \(line\) 要比 \(line'\) 更优，则说明左子树表示的区间有部分区间不如 \(line\) 优，往左子树递归，右端点同理，查询单点极值暴力查询即可

• 时间复杂度：\(O(mlogn)\)

代码

// Problem: P4097 [HEOI2013]Segment
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4097
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

typedef pair<double,int> PDI;
const int N=40005,M=1e5+5,mod1=39989,mod2=1e9;
const double eps=1e-8;
int n;

struct Line
{
	double k,b;
}line[M];
struct Tr
{
	int l,r,id;
}tr[N<<2];
void build(int p,int l,int r)
{
	tr[p]={l,r};
	if(l==r)
		return ;
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
double get(int id,int x)
{
	return line[id].k*x+line[id].b;
}
int cmp(double a,double b)
{
	if(a-b>eps)return 1;
	if(b-a>eps)return -1;
	return 0;
}
void update(int p,int l,int r,int id)
{
	if(l<=tr[p].l&&tr[p].r<=r)
	{
		if(!tr[p].id)tr[p].id=id;
		else
		{
			int &tid=tr[p].id;
			int mid=tr[p].l+tr[p].r>>1;
			double new_y=get(id,mid),old_y=get(tid,mid);
			if(cmp(new_y,old_y)==1)swap(tid,id);
			if(tr[p].l==tr[p].r)return ;
			int judgel=cmp(get(id,l),get(tid,l));
			int judger=cmp(get(id,r),get(tid,r));
			if(judgel==1||(!judgel&&id<tid))update(p<<1,l,r,id);
			if(judger==1||(!judger&&id<tid))update(p<<1|1,l,r,id);
		}
		return ;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)update(p<<1,l,r,id);
	if(r>mid)update(p<<1|1,l,r,id);
}
PDI MAX(PDI a,PDI b)
{
	if(cmp(a.fi,b.fi)==1)return a;
	else if(cmp(a.fi,b.fi)==-1)return b;
	return a.se<b.se?a:b;
}
PDI ask(int p,int x)
{
	if(x<tr[p].l||x>tr[p].r)return {0,0};
    PDI res={get(tr[p].id,x),tr[p].id};
    if(tr[p].l==tr[p].r)return res;
    res=MAX(res,ask(p<<1,x));
    res=MAX(res,ask(p<<1|1,x));
    return res;
}
int main()
{
	build(1,1,40000);
	int lstans=0,cnt;
	int t=0;
    for(scanf("%d",&n);n;n--)
    {
    	int x0,y0,x1,y1,k,op;
    	scanf("%d",&op);
    	if(op)
    	{
    		scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
    		x0=(x0+lstans-1)%mod1+1,x1=(x1+lstans-1)%mod1+1;
    		y0=(y0+lstans-1)%mod2+1,y1=(y1+lstans-1)%mod2+1;
    		if(x0>x1)swap(x0,x1),swap(y0,y1);
    		if(x0==x1)line[++cnt]={0,(double)max(y0,y1)};
    		else
    			line[++cnt]={(double)(y1-y0)/(x1-x0),y1-(double)(y1-y0)/(x1-x0)*x1};
    		update(1,x0,x1,cnt);
    	}
    	else
    	{
    		scanf("%d",&k);
    		k=(k+lstans-1)%mod1+1;
    		printf("%d\n",lstans=ask(1,k).se);
    	}
    	
    }
    return 0;
}