妙妙题。
我们考虑如何方便地描述一棵广义线段树。不难想到使用断点描述，即对于一个结点 \([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;
}