*：不错的题。
Codeforces Round 618
CF1299C Water Balance *2100
注意到答案序列一定是单调递增的，证明：如果不是单调递增的则一定可以通过一次操作将字典序变小。
故，使用单调栈维护当前最靠右区间的权值，如果两个相邻区间合并后字典序会更小就将其合并，时间复杂度 \(O(n)\)，Code。
*CF1299E So Mean *3400
Anton 题。
观察一：对于 \(i\)，询问除了 \(i\) 的所有数，答案为 \(1\) 当且仅当 \(i\) 为 \(1\) 或 \(n\)。
观察二：推广观察一，若已知 \([1,k]\) 和 \([n-k+1,n]\)，对于 \(i\in[k+1,n-k]\)，询问除了 \(i\) 与所有已知数的所有数，答案为 \(1\) 当且仅当 \(i\) 为 \(k+1\) 或 \(n-k\)。
观察三：\(1\) 和 \(n\) 可以任意确定。
因为 \(1\) 已经确定，那么只需要使用一次操作就可以确定 \(k+1\) 与 \(n-k\) 的位置，因为这两个必定奇偶性不同。
依据这个做法就可以得到一个 \(O(n^2)\) 的做法。
观察四：依据中国剩余定理，知道 \(p_i\bmod 3,5,7,8\) 的值就可以得到 \(p_i\) 的值。
观察五：询问 \(k\) 个总和差为 \(1\) 的子集和某个不知道的数就可以得到这个数 \(\bmod k\) 的值。
所以，我们根据观察二询问到 \(k=5\)，就可以求出 \(p_i\bmod 3,5,7,8\) 来得到 \(p_i\) 的值，可以通过，Code。
Codeforces Round 619
CF1301E Nanosoft *2500
感觉有点拉？
我们将红色格子右下角的位置赋值上这个对应最大正方形的边长，对于每一次询问，显然具有可二分性，每次二分一个边长，问题被归约成一个矩形最大值问题，二维 ST 表即可，时间复杂度为 \(O(nm\log n\log m)-O(\log n)\)。
当然可以使用前缀和直接暴力预处理加查询，时间复杂度 \(O(n^3)-O(n)\)，也可以通过，Code。
CF1301F Super Jaber *2600
如果 \(q=1\)，则可以直接最短路，有很多组询问则考虑预处理。
预处理 \(f(k,i,j)\) 表示 \((i,j)\) 走到 \(k\) 这个颜色所需的步数？好像不错。
对于每组询问，直接求出 \(\min_k f(k,r_1,c_1)+f(k,r_2,c_2)+1\) 就可以求出带瞬移的路径，但是还有不带瞬移的，曼哈顿路径就可以涵盖这种情况。
BFS 预处理，时间复杂度 \(O(knm)-O(k)\)，Code。
Educational Codeforces Round 82
CF1303E Erase Subsequences *2200
拉。
枚举 \(t\) 被割开的位置，那么，问题变成要从 \(s\) 中取出两个不相交的子序列。
直接 \(f_{i,j}\) 表示每个序列被匹配到的位置是经典 \(O(n^3)\)，算起来是 \(O(n^4)\)，但是 DP 只记 \(0/1\) 有点浪费，改成 \(f_{i,j}\) 表示用前 \(i\) 位匹配了 \(j\) 个 \(s_1\)，剩下的可以最多匹配出几个 \(s_2\)，那么就是 \(O(n^3)\)，Code。