考虑自然的图论模型，$n$ 个点，$i$ 连向 $a_i$。如果没有 $(j-i) > 1$，显然只需要 $n$ 减环长次操作就可以排序。注意到这个排序策略必须要每一次都环数 $+1$ 才行，也就是每一次操作都在环内。

当我们不能用环长 -1 次环内的不相邻交换操作排序，我们就称这个环是难的。认为自环不是难的，这样最终状态没有难的环。显然编号相邻的二元环是难的，所以有难的环。考察什么样的环是难的。

如果一个环在编号上占据的不是一段区间，那么它不是难的：假设存在一个 $l$ 不在环上且有 $>l$ 和 $<l$ 的点在环上，那么必然存在一条 $<l$ 到 $>l$ 的边，也存在一条 $>l$ 到 $<l$ 的边。任选其中一条边交换，可以让 $<l$ 或者 $>l$ 的点的个数减 1 并获得一个自环。一直做直到两边都剩一个点，这个时候交换它们俩就行了。

考虑值域连续的环，设其长度为 $l$。注意到若存在一个 $i \in [2,l-1]$ 它的位置不是 $i-1$ 或者 $i+1$，就可以通过把 $i$ 归位创造一个长度为 $(l-1)$ 的值域不连续的环。因此这样的环不是难的。

所以难的环一定有 $i \in [2,l-1]$ 的位置要么是 $i-1$ 要么是 $i+1$，即可以选左右。注意到若 $p$ 选右 $p+1$ 选左就会有二元环不符合这个环长条件，所以一定是一段前缀选左一段后缀选右，所以环长成 2 3 4 5 ... k n 1 (k+1) (k+2) ... (n-2) (n-1) 这个样子。

当这个环不是 2 3 4 5 ... (n-1) n 1 的时候，你总是可以通过归位最小或最大元素，把这个环归位成 2413，此时存在一个三步的做法：交换

操作顺序无关。一堆积木操作后会变成一段或两段连续的 $1$。两个这样的东西合并还是会变成一段 $1$ 被挖掉一个空的形状。

注意到操作前后坐标和不变，所以可以直接算出最后的位置。

由于 $x_i$ 已经排好序了，可以使用栈进行合并。

询问的时候也是从左到右扫一遍，时间复杂度 $O(n)$。

$H$ 的数据范围暗示，需要高效的算法来确定分界值 $u^*$。由于分界值 $u^*$ 和划分出的席位数（即 $u_i/2^j \ge u^*$ 的 $(i,j)$ 对数）之间具有良好的单调关系，可以用二分 $u^*$ 的办法求解。

每次二分 $u^*$，对每个 $u_i$ 判断可以分得多少席位。整理不等式可得

$$j \le \log\frac{u_i}{u^*}$$

故可以分得 $\left\lfloor\log(u_i/u^*)\right\rfloor$ 个席位。对每个 $u_i$ 可以 $O(1)$ 求解（假设忽略运算复杂度），则总复杂度为 $O(T\log H)$，可以通过本题。

直接对 $u^*$ 二分，可能会出现很大的精度问题：每个 $u_i$ 最少分得 $H/T$ 个席位，故

$$u^* \approx \frac{u_i}{2^{H/T}} \rightarrow 0$$

一种解决办法是，对 $v^*=\log u^*$ 进行二分，则可以转化为 $j = \left\lfloor\log u_i − v^*\right\rfloor，相对而言精度问题不大。

更进一步地，可以对 $v^*$ 的整数部分和小数部分分开求解。整数部分需要根据是否大于 $\left\lfloor\max\log u_i\right\rfloor简单讨论，小数部分直接排序即可。这样可以完全避免精度问题。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527165

大意

求最小值的石子合并，$n \le 40000$。

思路

利用 GarsiaWachs 算法。

在序列中找到第一个满足 $a_{i-1} \le a_{i+1}$ 的三元组 $(a_{i-1}, a_i, a_{i+1})$。

合并 $a_{i-1}$ 和 $a_i$，得分增加 $W = a_{i-1} + a_i$。

从当前位置向左寻找第一个大于 $W$ 的位置，将 $W$ 插入到其后面。

重复上述过程，直到只剩下一堆石子。

$n\leq 2$ 的情况可以特判。

可以发现，任意时刻，如果 The BOT 在位置 $x$，那么可以移动到相邻位置之一，无论 The NIT 怎么操作，The BOT 至少可以得到相邻位置的次小值并结束。

另外，当 $n\geq 3$ 时，可以先走到一个 $1<x<n$ 的位置，此时一定可以有三个选项。所以至少可以获得全局的第三小值。

于是一个答案的下界就是 $\max($相邻位置次小值，全局第三小值$)$，容易发现这也是一个上界，如果答案更大，那么将小于答案的看成 $0$，大于等于的看成 $1$，那么全局有 $\geq 3$ 个 $0$，且初始与位置相邻的位置至多有一个 $1$，The NIT 始终可以把一个 $0$ 交换过来，使得 The BOT 周围的三个数都是 $0$。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527051

大意

石子合并，$n = 1000$，求最小值。

思路

首先 $\mathcal{O}(n ^ 3)$ 的复杂度肯定是不可以的。

我们考虑优化，不难发现，对于 $w(i, j)$ 满足：

$$w(i, j - 1) + w(i + 1, j) \le w(i, j) + w(i - 1,j - 1)$$

所以这个 $w$ 满足四边形不等式，故 $f$ 也满足。

然后我们定义这个 $G(k) = f(i, k) + f(k + 1, j)$，所以 $G(k)$ 为凹函数，则最小值在一个区间内取得，我们可以记录 $[i, j]$ 区间的决策点，这样你在算第 $[i, j]$ 的时候，区间 DP 的点 $k$ 就可以在 $s[i][j - 1]$ 和 $s[i + 1][j]$ 之间取得。