题目大意

「GXOI / GZOI 2019」特技飞行（Luogu 5302）

给定 $n$ 条线段，它们的起点和终点的 $x$ 坐标分别为 $Sx$ 和 $Tx$，$y$ 坐标在输入中给定。在两条线段 $l_1, l_2$ 交点，可以交换 $l_1, l_2$ 接下来的部分（变成两条折线）。交换或不交换分别可以获得固定的分数 $a$ 和 $b$。要求最后在 $x = Sx$ 处和 $x = Tx$ 处，折线保持相同的顺序。

另外有 $m$ 个观测点可以观测到一定范围内情况（曼哈顿距离），在观测范围内的点额外获得 $c$ 分。问如何交换可以获得最高的得分。保证交点小于等于 $k$ 个。

$n, m \le 10^5, k \le 5 \times 10^5$。

思路分析

不难发现这是一道二合一的题目。

第一部分是安排交换方案。

交换数量最大的方案就是在所有交点处交换，这样一定是可行的。

交换数量最小的方案就是对于每个置换分别考虑。如果置换的大小为 $\text{Size}$，则需要交换 $\text{Size} - 1$ 次。

第二部分是对于每个交点计算是否被评委看到。

由于交点个数小，我们可以预处理出所有交点，然后将坐标系旋转 $45^{\circ}$ 进行二维数点即可。

代码实现

1	#include <cstdio>
2	#include <set>
3	#include <vector>
4	#include <algorithm>
5	using namespace std;
6
7	typedef double db;
8
9	struct point {
10	db x, y;
11	};
12
13	struct event {
14	int type, x, y;
15	friend bool operator< (const event &a, const event &b) {
16	return a.x > b.x;
17	}
18	};
19
20	struct ipoint {
21	int x, y;
22	friend bool operator< (const ipoint &a, const ipoint &b) {
23	return a.x > b.x;
24	}
25	};
26
27	const int maxn = 1e5, maxm = 2e5, maxk = 5e5;
28	const db eps = 1e-8;
29	int n, m, k, a, b, c, tot, Sx, Tx, C, A1, A2, A3;
30	int ord[maxn + 3], rnk[maxn + 3], r[maxn + 3], bit[maxk + 3];
31	bool vis[maxn + 3];
32	point p[maxm + 3], ip[maxk + 3], gst[maxn + 3];
33	event e[maxk + 3];
34	ipoint pnt[maxk + 3];
35	vector<db> Vx, Vy;
36	set<int> S;
37
38	void add(int x, int y) {
39	for (int i = x; i; i ^= i & -i) {
40	bit[i] += y;
41	}
42	}
43
44	int sum(int x) {
45	int y = 0;
46	for (int i = x; i <= k; i += i & -i) {
47	y += bit[i];
48	}
49	return y;
50	}
51
52	bool comp(int i, int j) {
53	return p[n + i].y < p[n + j].y;
54	}
55
56	void get_point(point &pnt, db ly1, db ly2, db ry1, db ry2) {
57	db num = -(ly1 - ly2) / (ry1 - ry2);
58	pnt.x = (Sx + Tx * num) / (num + 1);
59	pnt.y = (ly1 + ry1 * num) / (num + 1);
60	}
61
62	int main() {
63	scanf("%d %d %d %d %d %d", &n, &a, &b, &c, &Sx, &Tx);
64	for (int i = 1, y; i <= 2 * n; i++) {
65	scanf("%d", &y), p[i].y = y;
66	p[i].x = i <= n ? Sx : Tx;
67	}
68	for (int i = 1; i <= n; i++) {
69	ord[i] = i;
70	}
71	sort(ord + 1, ord + n + 1, comp);
72	for (int i = 1; i <= n; i++) if (!vis[i]) {
73	int x = ord[i];
74	while (x != i) {
75	vis[x] = true, C++, x = ord[x];
76	}
77	}
78	for (int i = 1; i <= n; i++) {
79	rnk[ord[i]] = i;
80	}
81	S.insert(rnk[1]);
82	for (int i = 2; i <= n; i++) {
83	set<int>::iterator it = S.end();
84	while (true) {
85	it--;
86	if (*it > rnk[i]) {
87	int x = ord[*it];
88	get_point(ip[++k], p[i].y, p[x].y, p[n + i].y, p[n + x].y);
89	}
90	if (*it < rnk[i] \|\| it == S.begin()) {
91	break;
92	}
93	}
94	S.insert(rnk[i]);
95	}
96	A1 = a * k;
97	A2 = a * C + b * (k - C);
98	scanf("%d", &m);
99	for (int i = 1, x, y; i <= m; i++) {
100	scanf("%d %d %d", &x, &y, &r[i]);
101	gst[i].x = x + y, gst[i].y = x - y;
102	}
103	for (int i = 1; i <= k; i++) {
104	db a = ip[i].x, b = ip[i].y;
105	ip[i].x = a + b, ip[i].y = a - b;
106	Vx.push_back(ip[i].x), Vy.push_back(ip[i].y);
107	}
108	sort(Vx.begin(), Vx.end());
109	sort(Vy.begin(), Vy.end());
110	for (int i = 1; i <= k; i++) {
111	pnt[i].x = lower_bound(Vx.begin(), Vx.end(), ip[i].x - .01) - Vx.begin() + 1;
112	pnt[i].y = lower_bound(Vy.begin(), Vy.end(), ip[i].y - .01) - Vy.begin() + 1;
113	}
114	for (int i = 1; i <= m; i++) {
115	db lx = gst[i].x - r[i] - eps, rx = gst[i].x + r[i] + eps;
116	db ly = gst[i].y - r[i] - eps, ry = gst[i].y + r[i] + eps;
117	int Lx = lower_bound(Vx.begin(), Vx.end(), lx) - Vx.begin() + 1 - 1;
118	int Rx = upper_bound(Vx.begin(), Vx.end(), rx) - Vx.begin();
119	int Ly = lower_bound(Vy.begin(), Vy.end(), ly) - Vy.begin() + 1 - 1;
120	int Ry = upper_bound(Vy.begin(), Vy.end(), ry) - Vy.begin();
121	e[++tot].type = 1, e[tot].x = Lx, e[tot].y = Ly;
122	e[++tot].type = -1, e[tot].x = Lx, e[tot].y = Ry;
123	e[++tot].type = -1, e[tot].x = Rx, e[tot].y = Ly;
124	e[++tot].type = 1, e[tot].x = Rx, e[tot].y = Ry;
125	}
126	sort(pnt + 1, pnt + k + 1);
127	sort(e + 1, e + tot + 1);
128	int cur = 1;
129	for (int i = 1; i <= k; i++) {
130	while (cur <= tot && e[cur].x >= pnt[i].x) {
131	add(e[cur].y, e[cur].type);
132	cur++;
133	}
134	if (sum(pnt[i].y)) {
135	A3++;
136	}
137	}
138	A3 *= c;
139	if (A1 > A2) {
140	swap(A1, A2);
141	}
142	printf("%d %d\n", A1 + A3, A2 + A3);
143	return 0;
144	}