非人类题，思维链跟我的 OI 生涯一样长（
题意
有一个长度为 \(N\) 的序列 \(A\) 和 \(M\) 次询问 \((L_i, R_i)\)，定义序列 \(B\) 为 \(B_i = \max_{j = L_i}^{R_i} A_j\)，现在你需要重排 \(A\) 使得 \(B\) 的字典序最大。
\(N, M \le 10^5\)。
思路
先想有无多项式做法~
朴素暴力
字典序问题的一个经典做法就是：对于每个 \(B_i\)，从大往小枚举 \(B_i\) 的取值，再 check 能否得到。欸？但是仔细往后推推就能发现，如果想要优化这个做法，就会有巨大的后效性，寄！
那就换一个角度：从大往小枚举取值，要让取这个取值的 \(B_i\) 下标集合 \(\{i\}\) 字典序最小，这样也能得到正确答案。
于是设 \(c_v = \sum_{i = 1}^n [A_i = v]\)，从大往小枚举 \(v\)，并尝试给下标最小的区间赋值成 \(v\)。从前往后枚举区间 \(L_i, R_i\)，每次 check 加进来 \(i\) 后，用 \(c_v\) 个点能不能使每个区间都包含至少一个数，若行就 \(B_i \gets v\)，否则删掉 \(i\) 后继续往后做。用形式化的语言描述，设 \(f(S)\) 表示 \(S\) 包含的区间中最小点覆盖数量，每次判断 \(f(S \cup \{[L_i, R_i]\})\) 是否 \(\le c_v\)，是就加入 \([L_i, R_i]\)，否则跳过。
求解区间点覆盖的最小数量是经典贪心，将区间按 \(L\) 排序之后贪心放右端点就行了，复杂度 \(O(M)\)（每次加区间时插入排序）。
在求完 \(i\) 的答案后从序列中删除所有 \(B_i = v\) 的区间，这样下一次求答案就不会有问题。
总复杂度可以均摊到 \(O(M^2)\)，可以通过 Sub 1，就不至于爆 \(0\) 了（。
优化
优化的方向有两个：
- 能不能通过一些性质，确定区间被加入的情况（比如一些区间一定被加，或一定不被加）？
- 通过数据结构优化或找特殊性质，优化掉求区间点覆盖的复杂度？
先从 1 入手，容易观察到被加入的区间一定是 一段前缀 与 后面零散的区间。而这段前缀的 \(f(S)\) 一定 \(< c_v\)，后面零散的区间的 \(f(S)\) 一定 \(= c_v\)。
那就考虑先求出来这段前缀吧，朴素的想法是二分，但这很容易被卡满了，需要优化。这时就有一个 Trick，叫倍增二分，用于搞一些均摊的东西。
那为什么能优化这个题呢？首先我们讲讲暴力的复杂度是怎么分析到 \(O(M^2)\) 的，我们设最后 \(S\) 中的 \(B_i\) 变成了 \(v\)，那么对 \(f(S)\) check 的复杂度是 \(O(|S|)\) 的，这一轮的总复杂度就是 \(O(M |S|)\)，由于 \(S\) 会在下一轮删除，故 \(\sum |S| = M\)，于是总复杂度就是 \(O(M^2)\) 的。
倍增二分的流程是什么呢？首先对 \(2^0, 2^1, 2^2\) 的前缀 check，假设终点是 \(l\)，就能求出 \(2^l\) 前缀的 \(f\) 是 \(< c_v\) 的，然后在 \([2^l, 2^{l + 1})\) 这个区间二分，总复杂度就是 \(O(l \cdot 2^l)\) 的，而 \(|S|\) 的大小至少是 \(2^l\)，那这个复杂度就一点问题没有，均摊下来 \(O(M \log M)\)（提前将前 \(2^{l + 1}\) 个区间排序，这样少一只 \(\log\)）。
接下来处理那些零散的区间，由于这时 \(c_v = f(S)\)，所以我们只需要看加入 \([L_i, R_i]\) 后 \(f(S)\) 是否变化即可。这个怎么 check 呢？
那我们考虑维护一下每个点的位置，这样就能快速看一个区间能否包含这个点了。
具体而言，先按 \(L_i\) 从小到大，能放就放 \(R_i\) 做一遍，求出 \(c_v\) 个点每个点的位置，第 \(i\) 个点的位置记为 \(y_i\)。再按照 \(R_i\) 从大到小，能放就放 \(L_i\)，求出第 \(i\) 个点的位置 \(x_i\)。那么第 \(i\) 个点的取值区间就是 \([x_i, y_i]\)。（这应该是很好理解的，就不证了）
所有区间 \([x_i, y_i]\) 应当是无交，且满足 \(y_i < x_{i + 1}\) 的。考虑加入区间 \([L, R]\) 对 \([x_i, y_i]\) 的影响：
- \([L, R]\) 与任何 \([x_i, y_i]\) 都无交，这时不能加入 \([L, R]\)。
- \([L, R]\) 包含了某个 \([x_i, y_i]\)，那么 \([L, R]\) 加入不影响 \([x_i, y_i]\) 的取值。
- \([L, R]\) 与恰好一个 \([x_i, y_i]\) 有交，此时将 \([x_i, y_i]\) 更新为 \([\max(L, x_i), \min(R, y_i)]\) 即可。
- \([L, R]\) 与两个 \([x_i, y_i]\) 有交，这时不能急着对某个 \([x_i, y_i]\) 取交集（因为有后效性），我们需要等待某个 \([x_i, y_i]\) 因后面的区间 \([L', R']\) 改变后，使 \([L, R]\) 只与其中一个区间有交时，再去做改变。具体地，用
set或priority_queue都能维护。
但是这样还是避免不了我们要扫一遍所有区间的尴尬处境，但可以通过分析上面的性质，继续优化下去。
对于每个区间 \([x_i, y_i]\)，找到编号最小的和 \(i\) 相交的区间 \([L_j, R_j]\)。在所有区间中找到编号最小的之后，删除它，并继续松弛所有 \([x_i, y_i]\)，此过程可用优先队列维护。
怎么找呢？可以用线段树维护，对于区间 \([L_j, R_j]\)，给它完全覆盖的区间打上 \(j\) 的标记，接着 \([x_i, y_i]\) 就在线段树上所有遍历过的区间取标记的 \(\min\) 即可。
于是总复杂度 \(O(M \log M)\)，代码应该非常难写啊。