[ARC164E] Segment-Tree Optimization
题目大意是让你构造一棵广义线段树，给定若干个询问使得询问出的区间最大深度最小并且最大神帝的个数最少。感官上，我们认为满二叉树很优美，所以可以朝着这个方向思考。
首先，不难看出有一些区间中所有数在所有询问中被绑在了一起，即要么全都有要么全都没有，所以可以先把这些数缩起来。我的实现方法是对每个询问随机一个哈希值然后区间加，那么这样的区间中的哈希值都是相等的。区间加用差分可以做。
这样我们简化了问题：除了开头和结尾每个数在最深层都至少被访问一次，假设剩下了 \(m\) 个数。那么第一问的贪心做法就是令最深层能放的数的个数尽可能大，所以满二叉树肯定是最优的，只需找到最小的 \(d\) 满足 \(2^d \ge m\) 即可。
现在来考虑第二问。发现如果放到满二叉树里面会产生 \(2^d - m\) 个“空”位置。这些空位置能够把一些数丢到上层，以至于不需要在最深层访问这些数。由此不难想到 DP，直接记录还剩多少个空位置为状态即可 \(O(n^2)\) 转移。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
mt19937 rnd(231);
constexpr int N = 4100;
int n, q, m;
int l[100100], r[100100];
unsigned h[N];
int s[N], t[N], val[N];
int f[N][N];
void upd(int &x, int y) {
x = min(x, y);
}
int main() {
read(n), read(q);
for(int i = 1; i <= q; ++i) {
read(l[i], r[i]);
unsigned hsh = rnd();
h[l[i]] += hsh, h[r[i] + 1] -= hsh;
}
h[1] ++;
for(int i = 1; i <= n; ++i)
h[i] += h[i - 1];
for(int i = 1; i <= n; ++i) {
if(h[i] == h[i - 1]) continue;
val[++m] = i;
}
if(m == 1) {
printf("0 %d\n",q);
return 0;
}
val[++m] = n + 1;
for(int i = 1; i <= q; ++i)
++s[lower_bound(val + 1, val + m + 1, l[i]) - val],
++t[lower_bound(val + 1, val + m + 1, r[i] + 1) - val - 1];
--m;
int d = 0, p = 1;
while(p < m) p <<= 1, ++d;
int k = p - m;
for(int i = 1; i <= m; ++i)
for(int j = 0; j <= k + 2; ++j)
f[i][j] = 1e9;
for(int i = 1; i <= m; ++i) {
for(int j = k; j >= 0; --j) {
if(i >= 2)
upd(f[i][j], f[i - 2][j] + s[i] + t[i - 1]);
if(j < k) upd(f[i][j], f[i - 1][j + 1]);
}
}
int ans = 1e9;
for(int i = 0; i <= k; ++i)
ans = min(ans, f[m][i]);
printf("%d %d\n",d,2 * ans);
}