自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:09:17，当前版本为作者最后更新于2019-04-17 01:33:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目地址：P5302 [GXOI/GZOI2019]特技飞行

这里是官方题解（by lydrainbowcat）

题意

给 $10^5$ 条直线，给 $x = st$ 和 $x = ed$ 两个位置

在两条直线 $l1,l2$ 交点，可以交换 $l1,l2$ 接下来的部分（变成两条折线）

交换或不交换分别可以获得固定的分数 $a$ 和 $b$

另外有 $10^5$ 个观测点可以观测到一定范围内情况（曼哈顿距离），在观测范围内的点额外计分 $c$

要求最后在 $x = st$ 处和 $x = ed$ 处，直线保持相同的顺序

问如何交换可以获得最高的得分。保证交点小于等于 $5*10^5$ 个

解法

这其实是两个题的拼接

首先，若 $a>b$ ，说明交换越多越好。实际上所有交点都可以交换，因为交点个数恰好是逆序对数，所有逆序对都交换一下最后正好变成正序

若 $a<b$ ，交换次数为 $n -$ 置换数，因为每个置换之间的互相独立的，可以不参与交换。每个置换内部其实都等价于一个环（5-1-2-3-4这样的），交换次数为 $len-1$ ，故总次数为 $\sum\ (len - 1) = n -$ 置换数。

所有交点可以用类似于排序的方法 $O(n)$ 预处理，坐标转 $45$ 度

接下来就是若干个点（事件），还有若干个正方形（拆成两个事件）的扫描线问题

扫描线 + 树状数组即可

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAX_NR 100010
const long double eps = 1e-9;
int N, A, B, C, ST_X, ED_X, M;

struct Point {
	long double x, y;
	Point() = default;
	Point(int x_, int y_) :
		x(x_), y(y_) {}
	Point(long double x_, long double y_) :
		x(x_), y(y_) {}
} point[MAX_NR * 2];

struct Event {
	long double x;
	int y0, y1, op;
	Event() = default;
	Event(int x_, int y0_, int y1_, int op_) :
		x(x_), y0(y0_), y1(y1_), op(op_) {}
	Event(long double x_, int y_) :
		x(x_), y0(y_), y1(y_), op(0) {}
	inline bool operator < (const Event &a) const {
		if (fabs(x - a.x) > eps) {
			return x < a.x;
		} else if (op != a.op) {
			return op > a.op;
		} else {
			return false;
		}
	}
};

std::vector<Point> inter;

inline Point get_intersection(Point a, Point b, Point c, Point d) {
	long double a1 = b.y - a.y;
	long double b1 = a.x - b.x;
	long double c1 = a1 * a.x + b1 * a.y;

	long double a2 = d.y - c.y;
	long double b2 = c.x - d.x;
	long double c2 = a2 * c.x + b2 * c.y;

	long double determinant = a1 * b2 - a2 * b1;

	if (determinant == 0) {
		return { -1, -1 };
	} else {
		long double x = (b2*c1 - b1 * c2) / determinant;
		long double y = (a1*c2 - a2 * c1) / determinant;
		return { x, y };
	}
}

namespace BIT {

	int N;
	int b[MAX_NR * 20];

	void init(int n) {
		N = n;
		memset(b, 0, sizeof(b));
	}

	int query(int x) {
		int res = 0;
		for (int i = x; i > 0; i -= i & (-i)) {
			res += b[i];
		}
		return res;
	}

	void update(int x, int v) {
		for (int i = x; i <= N; i += i & (-i)) {
			b[i] += v;
		}
	}
}

bool cmp(int i,int j) {
	return point[N + i].y < point[N + j].y;
}

int main() {
	scanf("%d%d%d%d%d%d", &N, &A, &B, &C, &ST_X, &ED_X);
	for (int i = 0, x, y; i < N * 2; ++i) {
		scanf("%d", &y);
		x = (i < N ? ST_X : ED_X);
		point[i] = { x, y };
	}

	std::vector<int> p(N), rank(N), a(N), v(N);
	for (int i = 0; i < N; ++i) {
		a[i] = rank[i] = i;
		v[i] = 0;
	}

	std::sort(rank.begin(), rank.end(), cmp);

	for (int i = 0; i < N; ++i) {
		p[rank[i]] = i;
	}

	int nr_cross = N;
	for (int i = 0; i < N; ++i) {
		if (v[i]) continue;
		nr_cross--;
		int x = p[i];
		while (x != i) {
			v[x] = 1;
			x = p[x];
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = i; ; ++j) {
			if (i == p[j]) {
				int aj = a[j];
				for (int k = j - 1; k >= i; --k) {
					Point cur = get_intersection(
					                point[a[k]], point[a[k] + N],
					                point[aj], point[aj + N]);
					inter.push_back(Point(cur.x + cur.y, cur.x - cur.y));
					std::swap(p[k], p[k + 1]);
					a[k + 1] = a[k];
				}
				break;
			}
		}
	}

	scanf("%d", &M);
	std::vector<long double> Y(M * 2 + inter.size());
	std::vector<Event> events(M * 2 + inter.size());
	for (int i = 0, x, y, r; i < M; ++i) {
		scanf("%d%d%d", &x, &y, &r);
		int x_ = x, y_ = y;
		x = x + y, y = x_ - y_;
		events[i] = { x - r, y - r, y + r, 1 };
		events[i + M] = { x + r, y - r, y + r, -1 };
		Y[i] = y - r;
		Y[i + M] = y + r;
	}
	for (int i = 0; i < inter.size(); ++i) {
		Y[2 * M + i] = inter[i].y;
	}
	std::sort(Y.begin(), Y.end());
	// Y.resize(std::unique(Y.begin(), Y.end()) - Y.begin());
	int pos = 0;
	for (int i = 0; i < Y.size(); i++)
		if (i == 0 || fabs(Y[i] - Y[i - 1]) > eps) Y[pos++] = Y[i];
	Y.resize(pos);
	for (int i = 0; i < 2 * M; ++i) {
		events[i].y0 = std::lower_bound(Y.begin(), Y.end(), events[i].y0) - Y.begin() + 1;
		events[i].y1 = std::lower_bound(Y.begin(), Y.end(), events[i].y1) - Y.begin() + 1;
	}
	for (int i = 0; i < inter.size(); ++i) {
		int y = std::lower_bound(Y.begin(), Y.end(), inter[i].y) - Y.begin() + 1;
		events[2 * M + i] = { inter[i].x, y };
	}
	std::sort(events.begin(), events.end());

	int nr_observed = 0;
	BIT::init(2 * Y.size());
	for (int i = 0; i < events.size(); i++) {
		Event e = events[i];
		if (e.op) {
			BIT::update(e.y0, e.op);
			BIT::update(e.y1 + 1, -e.op);
		} else {
			nr_observed += BIT::query(e.y0) > 0;
		}
	}

	int nr_inv = inter.size();
	int score_observed = nr_observed * C;
	int max_score = A * nr_inv;
	int min_score = A * nr_cross + B * (nr_inv - nr_cross);
	if (A < B) {
		std::swap(min_score, max_score);
	}
	std::cout << min_score + score_observed << ' ' << max_score + score_observed << std::endl;
	return 0;
}