Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

李超线段树

Posted on

考试的时候就听到巨佬们在说了，但一直不会，现在学了，赶快补一下。

简介

当我们在一定值域内的插入线段，从上往下看查询 $x = k$ 时与线段的最高交点，可支持返回该线段的编号。

要求时间复杂度：$O(nlog^2(m))$，$n$ 是线段数，$m$ 是值域。

这玩意根本不可做，所以考试时暴力拿了个 $10$ 分就溜号了（在此orz wfy-暴力拿80的巨佬）。

在此环境下，李超线段树诞生了。

实现：

我们在线段树上维护优势线段的编号，由于每一个点都进行更改的话时间复杂度会超标，故我们在每个区间内存储的是区间中点的优势线段，查询时必须递归到单节点。

修改

我们将两条线段在公共区间讨论可得：

  • 没有优势线段，直接更改编号。
  • 插入线段完全更优，直接更改编号。
  • 中点处更优，更改编号并递归处理。
  • 若两端更高，且中间更低，递归处理。

代码：

1
2
3
4
5
6
7
if(st <= l && r <= ed)
{
	if(dcmp(calc(line[x], mid), calc(line[tr[root]], mid)) > 0) swap(tr[root], x); // 由于懒没有递归到单点，保证优势线段存在后（就一定可以更新答案），更新上一条优势线段的优势区间
	if(dcmp(calc(line[x], l), calc(line[tr[root]], l)) > 0) modify(root << 1, l, mid, st, ed, x);
	if(dcmp(calc(line[x], r), calc(line[tr[root]], r)) > 0) modify(root << 1 | 1, mid + 1, r, st, ed, x);
	return ;
}

查询

查询到单点就行了，没有太多问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int query(int root, int l, int r, int x)
{
	if(l == r) return tr[root];
	int mid = l + r >> 1;
	if(x <= mid)
	{
		int tem = query(root << 1, l, mid, x);
		return dcmp(calc(line[tem], x), calc(line[tr[root]], x)) > 0 ? tem : tr[root];
	}
	else {
		int tem = query(root << 1 | 1, mid + 1, r, x);
		return dcmp(calc(line[tem], x), calc(line[tr[root]], x)) > 0 ? tem : tr[root];
	}
}

例题

luogu P4097 [HEOI2013]Segment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
#define LL long long
#define PII pair<double, double>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 5, M = 4e4;
const double eps = 1e-8;
struct Line{
	double k, b;
}line[N];
int tr[M * 4 + 5];
int cnt, last;
double calc(Line x, int d){
	return x.b + d * x.k;
}
int dcmp(double x, double y)
{
	if(fabs(x - y) < eps) return 0;
	if(x < y) return -1;
	return 1;
}
void modify(int root, int l, int r, int st, int ed, int x)
{
	int mid = l + r >> 1;
	if(st <= l && r <= ed)
	{
		if(dcmp(calc(line[x], mid), calc(line[tr[root]], mid)) > 0) swap(tr[root], x);
		if(dcmp(calc(line[x], l), calc(line[tr[root]], l)) > 0) modify(root << 1, l, mid, st, ed, x);
		if(dcmp(calc(line[x], r), calc(line[tr[root]], r)) > 0) modify(root << 1 | 1, mid + 1, r, st, ed, x);
		return ;
	}
	if(st <= mid) modify(root << 1, l, mid, st, ed, x);
	if(ed > mid) modify(root << 1 | 1, mid + 1, r, st, ed, x);
}
int query(int root, int l, int r, int x)
{
	if(l == r) return tr[root];
	int mid = l + r >> 1;
	if(x <= mid)
	{
		int tem = query(root << 1, l, mid, x);
		return dcmp(calc(line[tem], x), calc(line[tr[root]], x)) > 0 ? tem : tr[root];
	}
	else {
		int tem = query(root << 1 | 1, mid + 1, r, x);
		return dcmp(calc(line[tem], x), calc(line[tr[root]], x)) > 0 ? tem : tr[root];
	}
}
int T;

void make(int &x)
{
	x = (x + last - 1) % 39989 + 1;
}
void ma(int &y)
{
	y = (y + last - 1) % 1000000000 + 1;
}
void add(int x, int y, int o, int u) // 建立新线段
{
	if(x == o) line[++ cnt] = {0, max(y, u)};
	else line[++ cnt] = {1.0 * (u - y) / (o - x), y - 1.0 * (u - y) / (o - x) * x};
}
int main()
{
	scanf("%d", &T);
	while(T --)
	{
		int op;
		scanf("%d", &op);
		if(!op)
		{
			int x;
			scanf("%d", &x);
			x = (x + last - 1) % 39989 + 1;
			printf("%d\n", last = query(1, 1, M, x));
		}
		if(op)
		{
			int x, y, o, u;
			scanf("%d%d%d%d", &x, &y, &o, &u);
			make(x), ma(y), make(o), ma(u);
			if(x > o) swap(x, o), swap(y, u);
			add(x, y, o, u);
			modify(1, 1, M, x, o, cnt);
		}
	}
	return 0;
}