526互联

AtCoder Regular Contest 164 E Segment-Tree Optimization

发布时间 2023-07-11 22:01:23作者: zltzlt

洛谷传送门

AtCoder 传送门

妙妙题。

我们考虑如何方便地描述一棵广义线段树。不难想到使用断点描述，即对于一个结点 \([l, r]\)，它的左右儿子分别是 \([l, mid], [mid + 1, r]\)，其中 \(mid \in [l, r - 1]\)，然后把一层缩成一个 \(2^{d - 1}\) 的序列，每一层都是上层对应结点的 \(mid\)，这样每对相邻断点组成了每个区间。

要令深度最小，我们将题中每个区间都拆成两个断点 \(l_i - 1, r_i\)，然后我们贪心地选择这些断点作为线段树的断点的一部分。设不同断点数量为 \(k\)，那么第一问的答案 \(d\) 可以轻易得知，就是最小的满足 \(2^d - 1 \ge k\) 的非负整数。因为第 \(1 \sim d\) 层共有 \(\sum\limits_{i = 1}^d 2^{i - 1} = 2^d - 1\) 个断点。

接下来我们考虑把这 \(2^d - 1\) 个断点从小到大排成一个序列，易知下标为奇数的是第 \(d\) 层的断点。我们现在要最小化第 \(d\) 层的结点访问次数之和。

设第 \(d\) 层的一个断点在 \(i \in [1, q], l_i - 1, r_i\) 中出现 \(t\) 次，可知这个断点对访问次数之和的贡献是 \(2t\)。因为这个断点两侧的区间各被访问 \(t\) 次。

然后我们可以 dp 了，设 \(f_{i, j}\) 为当前考虑到 \(1 \sim d\) 层的所有断点中，第 \(i\) 个断点，有 \(j\) 个 \(i \in [1, q], l_i - 1, r_i\) 中的断点被考虑，区间访问次数之和。根据上面得出的第 \(d\) 层断点出现次数乘 \(2\) 就是它对访问次数的贡献的结论，可以很容易地转移，考虑第 \(i\) 个断点是否是 \(i \in [1, q], l_i - 1, r_i\) 中地断点即可。注意若第 \(i\) 个断点不是第 \(d\) 层的断点，即 \(i\) 为偶数，就对访问次数没有贡献。

时间复杂度 \(O(q \log n + n^2)\)。

code 
// Problem: E - Segment-Tree Optimization
// Contest: AtCoder - AtCoder Regular Contest 164
// URL: https://atcoder.jp/contests/arc164/tasks/arc164_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 4040;

int n, m, f[maxn << 1][maxn], a[maxn], tot;
map<int, int> mp;

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 0, l, r; i < m; ++i) {
		scanf("%d%d", &l, &r);
		if (l > 1) {
			++mp[l - 1];
		}
		if (r < n) {
			++mp[r];
		}
	}
	for (pii p : mp) {
		a[++tot] = p.scd;
	}
	int d = 0;
	for (d = 0;; ++d) {
		if ((1 << d) - 1 >= tot) {
			break;
		}
	}
	printf("%d ", d);
	if (d == 0) {
		printf("%d\n", m);
		return;
	}
	mems(f, 0x3f);
	f[0][0] = 0;
	for (int i = 1; i < (1 << d); ++i) {
		for (int j = 0; j <= tot; ++j) {
			f[i][j] = f[i - 1][j];
			if (j) {
				f[i][j] = min(f[i][j], f[i - 1][j - 1] + ((i & 1) ? a[j] : 0));
			}
		}
	}
	printf("%d\n", f[(1 << d) - 1][tot] * 2);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}