mydcwfy's Blog

CF102586L Yosupo's Algorithm

Posted on
Symbols count in article: 3.5k Reading time ≈ 8 mins.

二维平面上有 $n$ 个红点和 $n$ 个蓝点，每个点有一个权值 $vr_i/vb_i$，$q$ 次询问，每次给定 $L, R$，求满足 $[xr_i R]$ 并且 $[yr_i < yb_j]$ 的 $(i, j)$ 中 $vr_i + vb_j$ 的最大值。$n\leq 10 ^ 5$，$q\leq 5\times 10 ^ 5$。

对于这种 $yr_i < yb_j$ 限制比较明显的，可以考虑一维分治，一维扫描线计算二维符合情况的答案。

首先容易发现 $y$ 的用处就是比较 $yr_i$ 和 $yb_j$，于是考虑对 $y$ 分治。假设当前 $y$ 的区间是 $[l, r]$，我们强制要求 $yr_i\leq mid$，$yb_i > mid$，然后向两边递归即可。容易发现如果我们可以做到线性扫所有 $yr_i$ 和 $yb_j$，那么时间复杂度就是正确的 $O(n\log n)$，那么得到的二元组也是 $O(n\log n)$ 的。

现在问题在于如何线性得到所有可能是最优解的方案。一个可以发现的贪心思想是我们一定会选择满足 $yr_i\leq mid$ 中权值最大的点和 $yb_j > mid$ 中权值最大的点。容易发现如果两个都没有被选择的话，我们一定可以替换一个变成这两个点中的一个。这样我们只需要把两边最大的点选进去即可。这样备选的二元组是 $O(n\log n)$ 组。

剩下的就是一个二维数点，扫描线 + 线段树即可，时间复杂度 $O(n\log ^ 2 n + q\log n)$，可以通过。

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
91
92
93
94
95
96
97
98
99
100
struct Segment_Tree {
	struct Node {
		int l, r, mx;
	} tr[N << 2];
	
	void pushup(int x) { tr[x].mx = std::max(tr[x << 1].mx, tr[x << 1 | 1].mx); }
	
	void build(int x, int l, int r)
	{
		tr[x] = {l, r, -1};
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
	}
	
	void modify(int x, int pos, int c)
	{
		chkmax(tr[x].mx, c);
		if (tr[x].l ^ tr[x].r) modify(pos <= (tr[x].l + tr[x].r) >> 1 ? x << 1 : x << 1 | 1, pos, c);
	}
	
	int query(int x, int l, int r)
	{
		if (tr[x].l > r || tr[x].r < l) return -1;
		if (tr[x].l >= l && tr[x].r <= r) return tr[x].mx;
		return std::max(query(x << 1, l, r), query(x << 1 | 1, l, r));
	}
} seg;
 
void solve(int yl, int yr, std::vector<int> rid, std::vector<int> bid)
{
	if (rid.empty() || bid.empty()) return;
	int mxid = 0, mid = (yl + yr) >> 1;
	for (int &x : rid)
		if (r[x].y <= mid && r[x].v > r[mxid].v) mxid = x;
	if (mxid)
		for (int &x : bid)
			if (b[x].y > mid) vd.push_back({mxid, x});
	mxid = 0;
	for (int &x : bid)
		if (b[x].y > mid && b[x].v > b[mxid].v) mxid = x;
	if (mxid)
		for (int &x : rid)
			if (r[x].y <= mid) vd.push_back({x, mxid});
	
	std::vector<int> r1, r2, b1, b2;
	for (int &x : rid)
		if (r[x].y <= mid) r1.push_back(x);
		else r2.push_back(x);
	for (int &x : bid)
		if (b[x].y <= mid) b1.push_back(x);
		else b2.push_back(x);
	solve(yl, mid, r1, b1), solve(mid + 1, yr, r2, b2);
}
 
int main()
{
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) scanf("%d %d %d", &r[i].x, &r[i].y, &r[i].v);
	for (int i = 1; i <= n; ++ i) scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].v);
	std::cin >> Q;
	for (int i = 1; i <= Q; ++ i) scanf("%d %d", &q[i].l, &q[i].r), q[i].id = i, q[i].res = -1;
	std::vector<int> allid(n), ws(n);
	for (int i = 0; i < n; ++ i) allid[i] = i + 1;
	solve(1, 1e9, allid, allid);
 
	auto loc = [&](int x) {
		return std::lower_bound(ws.begin(), ws.end(), x) - ws.begin() + 1;
	};
	for (int i = 0; i < n; ++ i) ws[i] = b[i + 1].x;
	std::sort(ws.begin(), ws.end());
	seg.build(1, 1, n);
	std::sort(vd.begin(), vd.end(), [&](PII &x, PII &y) {
		return r[x.first].x < r[y.first].x;
	});
	std::sort(q + 1, q + Q + 1, [&](Query &q1, Query &q2) {
		return q1.l < q2.l;
	});
	int it = 0, ed = vd.size();
	for (int i = 1; i <= Q; ++ i)
	{
		while (it < ed && r[vd[it].first].x <= q[i].l)
			seg.modify(1, loc(b[vd[it].second].x), r[vd[it].first].v + b[vd[it].second].v), it ++;
		chkmax(q[i].res, seg.query(1, loc(q[i].r), n));
	}
	seg.build(1, 1, n);
	it = vd.size() - 1;
	for (int i = Q; i; -- i)
	{
		while (it >= 0 && r[vd[it].first].x >= q[i].l)
			seg.modify(1, loc(b[vd[it].second].x), r[vd[it].first].v + b[vd[it].second].v), it --;
		chkmax(q[i].res, seg.query(1, 1, loc(q[i].r) - 1));
	}
	
	std::sort(q + 1, q + Q + 1, [&](Query &q1, Query &q2) {
		return q1.id < q2.id;
	});
	for (int i = 1; i <= Q; ++ i) printf("%d\n", q[i].res);
	return 0;
}