A 神奇天平

一道热身题， 每次把物品尽可能平均的分成 $m+1m+1$ 堆， 把其中 $mm$​ 堆放到天平上，如果平衡，重球在不在天平的那一堆里，否则在最重的那一堆里。所以最劣情况下每次 $nn$ 至少被缩小为 $\lceil \frac{n}{m+1}\rceil \backslash lceil\backslash frac\{n\}\{m+1\}\backslash rceil$

code

B 魔法学院(easy version)

裸的线段树题，题意实际上是区间取 $maxmax$​ , 最后求区间和, 用线段树可以 $O((n+m)\log n)O((n\; +\; m)\; \backslash log\; n)$​​ 解决.

code

C 魔法学院(hard version)

数据加强了，刚才 $(n+m)\log n(n\; +\; m)\; \backslash log\; n$​​ 的做法没用了。发现只有最后才会进行一次询问，所以可以把修改操作离线下来。按照 $c_{i}c\_i$​​ 排序，这样保证后面修改的值比前面大，可以直接用区间覆盖来解决。用珂朵莉树，复杂度 $O(n\log \log n)O(n\backslash log\backslash log\; n)$​

code

D 监狱逃亡

监狱的宽等于 $33$ , 先考虑宽等于 $22$ 的做法。

宽等于 $22$ 很简单，枚举在哪列向下移动就行。

那么宽等于 $33$​​ , 就是枚举第二次在哪列向下移动，至于第一次在哪列要用数据结构来维护。

设第二次向下移动后路径价值和为 $xx$ , 移动前为 $yy$ , 只需满足 $x+y\ge 0x\; +\; y\; \backslash geq\; 0$ 即可，也就是 $x\ge -yx\; \backslash geq\; -y$ 可以用数组数组来维护。

第二次向下移动的列从 $i-1i\; -\; 1$​ 列移动到 $ii$​​ 列，那么所有的 $yy$ 都会加 $a[2][i]a[2][i]$ 但是直接加是不行的，所以可以用 $tagtag$ 记录一下整体加。 code