Edu Round 168
C. Even Positions
从左向右考虑，为使每个括号对的贡献尽量小，每当能填右括号时就填右括号，否则填左括号。最后统计答案。
codeforces.com/contest/1997/submission/300593589
D. Maximize the Root
注意到答案具有单调性，考虑二分答案，使用dfs来check，维护一个当前累积需要减少的数，每当一个数小于0，就把它强行加到0，然后更新需要减少的数，递归子树。当遇到叶子节点时，判断是否可以满足要求。
本题出错是因为这个累计需要减小的值会爆long long，甚至用了__int128_t也不行。考虑到叶子节点的点权是整数范围，当这个累计值超过INT_MAX时其实就已经可以return false了。
Submission #300604429 - Codeforces
E. Level Up
我观察到了如果固定下标i，这个怪物战斗与否所需的k具有单调性。于是考虑二分。但是，如果对于每个询问都要二分那么复杂度将会是 $O(n^2\cdot log{n})$。
我在洛谷的题解里找到了类似思路的一个整体二分的方法。思路是同时二分查找每个怪物恰好发生战斗所需的k的值。对于区间 $[L, R]$，维护所有可能的k落在$[L, R]$ 中的怪物序列。然后我们将区间二分，这时只需判断把这个怪物序列中的哪些怪物放入左半区间，哪些怪物放入右半区间，然后对左半区间和右半区间分别进行分治即可。这个判断方法如下：
我们需要计算出面对当前怪物时我们的角色等级，这一等级取决于：k值小于L的怪物的贡献以及k值在 $[L, mid]$ 之间的怪物的贡献。我们按照下标递增的顺序考虑当前序列中的怪物，那么，在怪物序列中，当前考虑的这个怪物之前的所有怪物都已经被考虑过了，也就是说我们知道它们有没有发生战斗。而在我们维护的怪物序列之外，也有一些怪物已经发生了战斗，那么这些怪物的k值一定小于L，因为如果大于等于L就会出现在当前序列中。当前怪物左侧的k值小于L的怪物数量给记录下来，那么我们目前已经战斗过的怪物数量就等于，当前序列中已经战斗过的怪物数量加上当前怪物左侧k值小于L的怪物数量。进而我们可以算出当前等级，判断这个怪物是否会发生战斗。然后，如果发生战斗，这只怪物的可能k值应该落在 $[L, mid]$；如果不发生战斗，那么这只怪物的可能的k值应该落在 $[mid, R]$ ，对于它来说新的L就是mid，因此它前面的发生战斗的怪物数量用来更新这个怪物的左侧k值小于L的怪物数量。
本题还有一些数据结构的做法，有树状数组的，有根号分块的，下次补。