Description
JOI 美术馆计划近期举办一场绘画展览。馆方拥有编号为 \(1\) 至 \(N\) 的 \(N\) 幅画作，其中画作 \(i\)（\(1 \leq i \leq N\)）的美观值为 \(A_i\)。在展览中这些画作将排成一行展示，但具体排列顺序尚未确定。
共有 \(M\) 家杂志将对展览进行报道。这些杂志按影响力从大到小依次编号为 \(1\) 至 \(M\)。每家杂志将发布展览中某一连续段画作的摄影照片。具体来说，杂志 \(j\)（\(1 \leq j \leq M\)）将发布排列中从左数第 \(L_j, L_j + 1, \ldots, R_j\) 幅画作的照片。杂志 \(j\)（\(1 \leq j \leq M\)）报道的吸引力定义为该杂志所覆盖画作的最大美观值。
JOI 君作为 JOI 美术馆的馆长，希望通过排列画作使得这些杂志的报道更具吸引力，从而吸引更多参观者。由于影响力更大的杂志能触达更多受众，他优先希望提升更具影响力杂志的报道吸引力。
具体而言，设 \(b_j\) 为杂志 \(j\)（\(1 \leq j \leq M\)）报道的吸引力，则 JOI 君希望排列画作，使得序列 \(b = (b_1, b_2, \ldots, b_M)\) 的字典序最大化。
在这里，对于不同的数列 \(b = (b_1, b_2, \ldots, b_M)\) 和 \(b' = (b'_1, b'_2, \ldots, b'_M)\)，所谓“\(b\) 在字典序上大于 \(b'\)”，是指存在满足 \(b_k \neq b'_k\) 的最小下标 \(k\)（\(1 \leq k \leq M\)），且对于该 \(k\) 有 \(b_k > b'_k\)。
请编写一个程序，根据待展览画作的信息和报道展览的杂志信息，计算当画作排列使序列 \(b = (b_1, b_2, \ldots, b_M)\) 字典序最大化时，每家杂志报道的吸引力。
\(1 ≤ N ≤ 10^5,1 ≤ M ≤ 10^5,1 ≤ A_i ≤ N\)。
Solution
下面假定 \(n,m\) 同阶。
设 \(f(S)\) 表示要满足在 \(S\) 集合内的区间里每个区间至少有一个点的最少总点数。
首先肯定是贪心地给编号最小的区间 \(i\) 选择最大的 \(v\)，使得 \(f(S_v\cup\{[l_i,r_i]\})\leq cnt_v\)，并让 \(S_v\leftarrow S_v\cup\{[l_i,r_i]\}\)。
求 \(f(S)\) 的话就直接按照右端点从小到大排序，如果当前区间 \([l,r]\) 不包含任何一个点，就在 \(r\) 处放一个点。最后放的点数就是答案。
可以发现这么做选的第 \(i\) 个点的位置 \(sr_i\) 实际上是所有可能方案中第 \(i\) 个点的最大可能下标，倒过来按照左端点从大到小排序贪心能够得到最小可能下标 \(sl_i\)。下面这个东西有两个性质：
性质 1：\(\forall 1\leq i<k,sr_i<sl_{i+1}\)。
证明
如果存在 \(sl_i\leq sl_{i+1}\leq sr_i\leq sr_{i+1}\)，找到最大的满足这个条件的 \(i\)，则满足 \(sr_{i+1}<sl_{i+2}\) 且存在一个区间 \(j\)，满足 \(r_j=sr_i\) 且 \(l_j>sr_i\geq sl_{i+1}\)，所以倒过来贪心的时候 \(i+1\) 这个位置的点一定会选到选 \(l_j\) 而不是 \(sl_{i+1}\)。
性质 2：给 \(S\) 加入一个区间 \([L,R]\)，\(f(S)\) 不变的充要条件是存在 \(i\)，满足 \([sl_i,sr_i]\) 与 \([L,R]\) 有交。
证明
只需要说明存在一个选点方案，使得 \([L,R]\) 包含其中至少一个点。
找到有交的 \(i\)，所有 \(j<i\) 的点放在 \(sr_j\)，\(j>i\) 的点放在 \(sl_j\)。这 \(k-1\) 个点的放置方案可以解决所有已经加到 \(S\) 中 \(l\leq sl_{i-1}\) 或者 \(r\geq sr_{i+1}\) 的区间。容易发现剩下的区间 \([l,r]\)，一定满足 \(l\leq sl_i\leq sr_i\leq r\)，所以第 \(i\) 个点可以在 \([sl_i,sr_i]\) 内随便选，放在和 \([L,R]\) 的交里即可。
如果找不到这样的 \(i\) 显然 \(f(S)\) 会增加。
考虑从大到小枚举 \(v\)，设限制是 \(lim\)，答案为 \(v\) 的区间数是 \(c\)，我们希望用 \(O(c\times\text{polylog}(c))\) 的时间复杂度找到这些区间。
首先如果 \(f(S)\) 一直会增加的话 \(sl_i\) 和 \(sr_i\) 会很不好维护，所以考虑先二分找到一个极长的前缀使得这个前缀的 \(f(S)\) 不超过 \(lim\)。
那么这个前缀的 \(f(S)\) 一定等于 \(lim\) 或者这个前缀把所有区间选完了。
但是直接二分复杂度不是均摊的，因为二分的过程中会用至少 \(O(n\log n)\) 的代价 check，\(c\) 如果是 \(1\) 的话就会退化成 \(O(n^2\log n)\)。
考虑倍增，暴力 check，找到最大的 \(b\) 满足 \(2^b\leq c\)，那么 \(2^b\leq c<2^{b+1}\)，在这个区间内再进行二分即可。总时间复杂度变为 \(O(c\log^2n)\)，均摊就对了！
先维护出这个前缀的区间构成的 \([sl_i,sr_i]\)，我们用优先队列维护与某个区间 \([sl_i,sr_i]\) 的相交的编号最小的区间。每次弹出队首并暴力更新 \(sl_i\) 和 \(sr_i\)，由于 \(sl_i\) 只会变大，\(sr_i\) 只会变小，而分别总共只有 \(O(c)\) 种取值，所以 \([sl_i,sr_i]\) 的历史总变化量为 \(O(c)\)。如果某个 \([sl_j,sr_j]\) 被更新了，就再往优先队列里加入一个与当前的 \([sl_j,sr_j]\) 相交的最小区间。
但是如果一个区间 \([l_j,r_j]\) 完全包含了很多区间，且编号很小，它就会加入队列很多次，复杂度又不对了。但是注意到这个区间最终一定会被加入，并且不会对 \([sl_i,sr_i]\) 造成影响，所以每次 \([sl_i,sr_i]\) 更新前先把所有这样的区间删掉即可。剩下的区间如果有交则说明要么左端点在区间内，要么右端点在区间内，只会算至多两次。
单次的时间复杂度为 \(O(c\log^2n)\)，总的时间复杂度也就是 \(O(n\log^2n)\)。
Code
#include <bits/stdc++.h>// #define int int64_tusing pii = std::pair<int, int>;const int kMaxN = 1e5 + 5;int n, m;
int cnt[kMaxN], l[kMaxN], r[kMaxN], res[kMaxN];
bool vis[kMaxN];struct List {int fir, pre[kMaxN], nxt[kMaxN];void init(int n) {fir = 1;for (int i = 1; i <= n; ++i) {pre[i] = i - 1, nxt[i] = (i == n ? 0 : i + 1);}}void del(int x) {if (x == fir) fir = nxt[x];if (pre[x]) nxt[pre[x]] = nxt[x];if (nxt[x]) pre[nxt[x]] = pre[x];}std::vector<int> getid(int k) {std::vector<int> v;for (int i = fir; i && k; i = nxt[i], --k) v.emplace_back(i);if (k) return {};return v;}
} list;struct SGT1 {std::vector<int> st[kMaxN * 4];void ins(int x, int l, int r, int ql, int v) {st[x].emplace_back(v);if (l == r) return;int mid = (l + r) >> 1;if (ql <= mid) ins(x << 1, l, mid, ql, v);else ins(x << 1 | 1, mid + 1, r, ql, v);}int query(int x, int l, int r, int ql, int qr) {for (; st[x].size() && vis[st[x].back()]; st[x].pop_back()) {}if (!st[x].size() || l > qr || r < ql) return 1e9;else if (l >= ql && r <= qr) return st[x].back();int mid = (l + r) >> 1;return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));}
} sgt1, sgt2;struct SGT2 {std::vector<pii> st[kMaxN * 4];void ins(int x, int l, int r, int ql, pii v) {st[x].emplace_back(v);if (l == r) return;int mid = (l + r) >> 1;if (ql <= mid) ins(x << 1, l, mid, ql, v);else ins(x << 1 | 1, mid + 1, r, ql, v);}pii query(int x, int l, int r, int ql, int qr) {for (; st[x].size() && vis[st[x].back().second]; st[x].pop_back()) {}if (!st[x].size() || l > qr || r < ql) return {1e9, 0};else if (l >= ql && r <= qr) return st[x].back();int mid = (l + r) >> 1;return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));}
} sgt3;struct BIT {int c[kMaxN];void clear() { std::fill_n(c + 1, n, 1e9); }void upd(int x, int v) {for (; x <= n; x += x & -x) c[x] = std::min(c[x], v);}int qry(int x) {int ret = 1e9;for (; x; x -= x & -x) ret = std::min(ret, c[x]);return ret;}void clear(int x) {for (; x <= n; x += x & -x) c[x] = 1e9;}
} bit1, bit2;void del(int x) {vis[x] = 1, list.del(x);
}int calc(std::vector<int> id) {if (!id.size()) return 1e9;std::sort(id.begin(), id.end(), [&] (int i, int j) { return r[i] < r[j]; });int cnt = 0, nowr = 0;for (auto i : id) {if (l[i] > nowr) ++cnt, nowr = r[i];}return cnt;
}std::vector<std::pair<int, int>> getseg(std::vector<int> id) {std::vector<int> sl, sr;{std::sort(id.begin(), id.end(), [&] (int i, int j) { return l[i] > l[j]; });int nowl = 1e9;for (auto i : id) {if (r[i] < nowl) sl.emplace_back(l[i]), nowl = l[i];}std::reverse(sl.begin(), sl.end());}{std::sort(id.begin(), id.end(), [&] (int i, int j) { return r[i] < r[j]; });int nowr = 0;for (auto i : id) {if (l[i] > nowr) sr.emplace_back(r[i]), nowr = r[i];}}assert(sl.size() == sr.size());std::vector<std::pair<int, int>> seg;for (int i = 0; i < sl.size(); ++i) seg.emplace_back(sl[i], sr[i]);return seg;
}void solve(int v, int cnt) {int len = 0;{ // 倍增找最长前缀int k = 0;for (int b = 1; b <= std::__lg(m); ++b) {if (calc(list.getid(1 << b)) <= cnt) k = b;else break;}int L = (1 << k), R = (1 << (k + 1)), res = L;while (L + 1 < R) {int mid = (L + R) >> 1;if (calc(list.getid(mid)) <= cnt) L = res = mid;else R = mid;}len = res;}auto vid = list.getid(len);for (auto i : vid) del(i), bit1.upd(n - l[i] + 1, r[i]), bit2.upd(r[i], -l[i]);auto seg = getseg(vid);static int sl[kMaxN], sr[kMaxN];// std::cerr << "??? " << v << ' ' << cnt << ' ' << seg.size() << '\n';cnt = seg.size();for (int i = 1; i <= seg.size(); ++i) std::tie(sl[i], sr[i]) = seg[i - 1];sl[cnt + 1] = sr[cnt + 1] = n + 1;std::priority_queue<pii, std::vector<pii>, std::greater<>> q;std::function<void(int)> fix = [&] (int i) {while (true) {auto [rr, id] = sgt3.query(1, 1, n, 1, sl[i]);assert(id <= m);if (id && r[id] >= sr[i]) res[id] = v, del(id);else break;}int id1 = sgt1.query(1, 1, n, sl[i], sr[i]), id2 = sgt2.query(1, 1, n, sl[i], sr[i]);if (std::min(id1, id2) <= m) q.emplace(std::min(id1, id2), i);};std::function<void(int)> upd = [&] (int i) {if (vis[i]) return;int it = std::lower_bound(sr + 1, sr + 1 + cnt, l[i]) - sr;if (it > cnt || std::max(sl[it], l[i]) > std::min(sr[it], r[i])) return;del(i), vid.emplace_back(i);bit1.upd(n - l[i] + 1, r[i]), bit2.upd(r[i], -l[i]);for (int j = std::lower_bound(sr + 1, sr + 1 + cnt, r[i]) - sr; j <= cnt; ++j) {// for (int j = 1; j <= cnt; ++j) {int val = bit1.qry(n - sr[j - 1]);assert(val <= sr[j]);if (val == sr[j]) break;sr[j] = val;assert(sl[j] <= sr[j]);fix(j);}for (int j = std::upper_bound(sl + 1, sl + 1 + cnt, l[i]) - sl - 1; j >= 1; --j) {// for (int j = 1; j <= cnt; ++j) {int val = -bit2.qry(sl[j + 1] - 1);assert(val >= sl[j]);if (val == sl[j]) break;sl[j] = val;assert(sl[j] <= sr[j]);fix(j);}};for (int i = 1; i <= cnt; ++i) {while (true) {auto [rr, id] = sgt3.query(1, 1, n, 1, sl[i]);if (id && r[id] >= sr[i]) res[id] = v, del(id);else break;}}for (int i = 1; i <= cnt; ++i) fix(i);for (; !q.empty();) {auto [id, p] = q.top(); q.pop();upd(id), fix(p);}for (auto i : vid) res[i] = v, bit1.clear(n - l[i] + 1), bit2.clear(r[i]);// for (auto i : vid) std::cerr << i << '\n';// for (auto [l, r] : seg) std::cerr << l << ' ' << r << '\n';// std::cerr << "-------------\n";
}void dickdreamer() {std::cin >> n >> m;for (int i = 1; i <= n; ++i) {int x;std::cin >> x;++cnt[x];}std::vector<int> vec;for (int i = 1; i <= m; ++i) {std::cin >> l[i] >> r[i];vec.emplace_back(i);}for (int i = m; i; --i) sgt1.ins(1, 1, n, l[i], i), sgt2.ins(1, 1, n, r[i], i);std::sort(vec.begin(), vec.end(), [&] (int i, int j) { return r[i] < r[j]; });for (auto i : vec) sgt3.ins(1, 1, n, l[i], {-r[i], i});list.init(m), bit1.clear(), bit2.clear();std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";for (int i = n; i; --i) {if (!cnt[i]) continue;solve(i, cnt[i]);}for (int i = 1; i <= m; ++i) std::cout << res[i] << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}