CWOI S C0279 D 怨

题意

使用 openssl enc -aes256 -pbdkf2 -a 加密。

U2FsdGVkX19GxF/VYhl6DxDxUwjXt+oXc8qSnlW2UPwSOTgmXNR7DfXj/ZavSTjn
nxUrN2o3eTxwfMDMdj0G+QKY56luHRqitF3lnVy98Vd6A2Mk9q4ugqVHqksj/zME
fvc1ACz6SS/IgKlrkSsfIunBzBM8qjULAt73e1Oa/2dm8dH3s3qS/f7cFaHWfukG
BbthNPuQR0YCNM66+lzYsdrtmxhDwfAG3zmXdQJ3V6c=

generator

仅作示意。

import itertools
import random
import sys

MAXN = 10**9

if len(sys.argv) != 3:
    print(f"Usage: {sys.argv[0]} n seed")

n = int(sys.argv[1])
random.seed(sys.argv[2])

print(n, n * (n - 1) // 2)
for i in range(n):
    print(*sorted(random.sample(range(MAXN), 2)))

for (l, r) in itertools.combinations(range(1, n + 1), 2):
    print(l, r)

解析

把询问挂到右端点离线下来。实际上，区间的并的连续段实际上就是区间端点数的一半，所以我们只需要关心每个端点左右的区间最后一次被覆盖的位置。从左往右扫所有区间和询问，$f_i$ 表示询问左端点为 $i$ 的端点个数，$s$ 表示维护的端点集。将区间 $[l_i, r_i]$ 加入后 $s$ 中 $l_i$ 到 $r_i$ 的点及其贡献都要删除，然后将 $l_i$ 和 $r_i$ 加入，如果一个端点左边区间的最后覆盖位置为 $x$，右边为 $y$，则区间 $[x, y)$ 或 $[y, x)$ 都会多出一个端点，需要对 $f$ 进行区间加，单点查操作。

建议看代码，这个有点抽象。

实现

struct interval_t
{
	int l, r;

	auto operator<=>(const interval_t &i) const = default;

	static interval_t sorted(int l, int r) 
	{
		return interval_t{std::min(l, r), std::max(l, r)};
	}
};

struct query_t
{
	int l, r, id;
};

struct iset
{
	struct node_t
	{
		int i;
		mutable int l, r;

		auto operator<=>(const node_t &n) const { return i <=> n.i; }

		node_t() = default;
		node_t(int i) : i(i) {}
		node_t(int i, int l, int r) : i(i), l(l), r(r) {}
	};

	std::set<node_t> s;

	std::vector<std::pair<int, interval_t>> insert(int t, interval_t in) 
	{
		std::vector<std::pair<int, interval_t>> res;

		auto [p1, f1] = s.emplace(in.l);
		if (!f1) {
			res.emplace_back(-1, interval_t::sorted(p1->l, p1->r));
		}
		p1->r = t;
		if (p1 != s.begin()) {
			p1->l = std::prev(p1)->r;
		} else {
			p1->l = -1;
		}
		res.emplace_back(1, interval_t::sorted(p1->l, p1->r));

		auto [p2, f2] = s.emplace(in.r);
		if (!f2) {
			res.emplace_back(-1, interval_t::sorted(p2->l, p2->r));
		}
		p2->l = t;
		if (std::next(p2) != s.end()) {
			p2->r = std::next(p2)->l;
		} else {
			p2->r = -1;
		}
		res.emplace_back(1, interval_t::sorted(p2->l, p2->r));

		for (auto p = std::next(p1); p != p2; ) {
			res.emplace_back(-1, interval_t::sorted(p->l, p->r));
			p = s.erase(p);
		}

		return res;
	}
};

struct fenwick_tree
{
	int n;
	std::vector<long long> t;
	fenwick_tree(int n) : n(n), t(n) {}

	void add(int x, long long v)
	{
		for (x++; x <= n; x += x & -x) t[x - 1] += v;
	}

	long long sum(int x)
	{
		long long res = 0;
		for (; x >= 1; x -= x & -x) res += t[x - 1];
		return res;
	}
};

int main()
{
	std::ios::sync_with_stdio(false);

	int n, m;
	std::cin >> n >> m;

	std::vector<interval_t> a(n);
	std::vector<std::vector<query_t>> q(n + 1);
	for (auto &[l, r] : a) std::cin >> l >> r;
	for (int i = 0; i < m; i++) {
		int l, r;
		std::cin >> l >> r;
		l--;
		q[r].emplace_back(l, r, i);
	}
	std::vector<int> ans(m);

	iset time;
	fenwick_tree f(n + 1);
	int d = 0;
	for (int i = 0; i <= n; i++) {
		for (auto [l, r, id] : q[i]) ans[id] = f.sum(l) + d;
		if (i == n) break;
		auto diff = time.insert(i, a[i]);
		for (auto [v, in] : diff) {
			if (in.l == -1) d += v;
			else f.add(in.l, v);
			f.add(in.r, -v);
		}
	}

	for (auto i : ans) std::cout << i / 2 << std::endl;
}