2022icpc南京)
日常被打爆，赛时3题，铜牌题被卡 \(O(n\log n\log A)\) 一直疯狂 \(TLE\)，赛后发现自己的思路跟正解完全背道而驰。
\(I\) 纯签到。
\(G\)：无解情况的判断特别简单，将所有的 \(0\) 看作 \(1\)，然后判断前缀和的每一项是否都大于 \(0\) 即可。显然操作 \(2\) 会增大答案，操作 \(1\) 会减小答案。那么考虑在序列合法的情况下，尽可能扩大操作 \(2\) 的次数（将序列中的 \(0\) 变成 \(-1\)）。我们发现，每个位置对于前缀和数组，只会影响以这个位置为结尾的后缀。那么显然贪心地倒着作修改更划算，对前缀和数组的影响规模最小。具体细节见代码。
code
\(A\)：南京站的特色袋鼠题，也不咋难。首先考虑将所有可能出界的袋鼠先排除，那么剩下的袋鼠在整个移动过程中一定不会出界，并且形状一定是矩形（证明略）。于是，每只袋鼠分别移动的过程，就可以优化成整个矩阵移动的过程。利用二维差分优化即可，最终可以得出每个位置可能经过的袋鼠个数。但需要注意一点：需要对不同时刻的同一位置上的矩形去重，因为对于矩形内的每个位置，对应的袋鼠都是之前已经经过的，不能重复考虑同一只袋鼠。用 \(set\) 简单维护即可。
code
D. Chat Program
被卡双 \(\log\) 了qwq...
求序列第 \(k\) 大的最大值，二分答案是显然的，只需要 \(check\) 是否存在一种操作区间，让 \(\geq mid\) 的数的数量 \(\geq k\) 即可。
蒟蒻的思路是：提前预处理好 \(aa_{i} = a_{i} + (i - 1) * d\) 的值，那么在检验操作区间内 \(\geq mid\) 的数的数量时，只需要检验 \(aa[l, r]\) 内 \(\geq mid - c + (l - 1) * d\) 的数的数量，等价于查询 \((mid - c + (l - 1) * d) - 1\) 的排名 \(x\)，答案就是 \(x - 1\)。（注意这里的排名是按值升序排序的，因此要将所有值取负后再插入）可是复杂度多了个 \(\log\)。。。
正解：需要考虑到在操作区间右移的过程中，每个值的变化最多只能是先增大再减小。那么使得 \(a[i] \geq mid\) 的所有可行的操作区间左端点一定是一个区间（可以自己画图看）。那么我们就只需要对每个 \(a[i]\) 作一个关于操作区间左端点的差分就可以了，最后只需前缀和还原并判断最大值是否 \(\geq k\)。这样 \(check\) 复杂度是 \(O(n)\) 的，总复杂度 \(O(n\log A)\)。
code
M. Drain the Water Tank
又是计算几何铜牌题。赛时有点思路，但还是隐约感觉有问题遂放弃。
code
B. Ropeway
code