A. Tales of a Sort

关键就是找逆序对

记一组逆序对下标为 \(l,r\)，则求出最大的 \(a_l\) 即可

B. Good Arrays

记要构造的 Good Array 为 \(b\)

前置：\(\forall 1\le i\le n,b_i=1\)

然后 \(O(n)\) 扫一遍看一下有没有重复，有重复就 \(b_i\leftarrow b_i+1\)

扫完之后，记 \(sum=\sum_{i=1}^n(a_i-b_i)\)，如果 \(sum\ge 0\) 就有解；反之无解

C. To Become Max

假设 \(a_i\) 变成最大值 \(x\)，那么后面一定是形如 \(x-1,x-2,\cdots\) 直到某个数不需要操作也能达到要求

这样一来，就是基于试错的方法计算答案，并且答案所在位置有单调性，很容易想到二分答案

然后就是枚举答案所在位置，模拟求解

复杂度 \(O(n\log m)\)，其中 \(m=\max_{i=1}^n a_i+k\)

D. More Wrong

又是交互题

其实这道交互题和前面那些牛鬼蛇神比算比较简单的了

因为是求解整个序列的最大值位置，而交互一次 ? l r 返回的结果是 \([l,r]\) 的逆序对个数

这种问题显然可以分解，所以要么 DP 要么分治

如果考虑 DP，那就应该是区间 DP，但是 \(n\le 2000\)，区间 DP 的复杂度基本上在 \(O(n^3)\)，没法做（事实上也很难设状态和转移方程）

考虑分治，对于 \(l=r\) 的边界情况，显然就返回 \(l\)

否则，记 \(mid=\lfloor\frac{l+r}{2}\rfloor\)，对于 \([l,mid]\) 和 \([mid+1,r]\) 分别求解，设 \(a\) 为 \([l,mid]\) 的解，\(b\) 为 \([mid+1,r]\) 的解，因为我们考虑分治，所以 \(a,b\) 其中一个是最大值，另一个是次大值

接下来就交互两次，一次是 \([a,b]\)，另一次是 \([a,b-1]\)（\([a+1,b]\) 也行），然后判断逆序对数量是否相等即可

总交互次数就是 \(2n^2[1+\frac{1}{2}+(\frac{1}{2})^2+\cdots]<4n^2\)，可以通过