CF1783E Game of the Year
我们先排除 \(a_i \leqslant b_i\) 的点。
即 \(\forall i, \lfloor \frac {a_i} {i} \rfloor \leqslant \lfloor \frac {b_i} {i} \rfloor\)。
考虑一个 \(k\) 把整个序列分成了 \(\frac n k\) 块，这样所有点都只需要在一个块。容易想到使用扫描线解决这个问题，所有我们有了 2log 的解法。
实际上，不合法的充要条件是 \((b_i,a_i]\) 中有 \(k\) 的倍数。所以直接对 \((b_i,a_i]\) 区间覆盖，最后看有无 \(k\) 的倍数被覆盖即可，时间复杂度 \(\mathcal {O}(n\log_2 n)\)。
CF1783F Double Sort II
考虑一个点只会被还原一次，所以直接跑个匹配就好了。
匈牙利算法的时间复杂度是 \(\mathcal {O}(n^2)\) 的，因为边最多只有 \(n\) 条。
[SDOI2017] 树点涂色
树链剖分，对每个点维护到根的颜色个数。发现我们暴力修改是对的，应该是 2 log 的。
机棚障碍 Hangar Hurdles
kruskal 重构树板，哪来的黑。
[BJOI2014] 大融合
LCT 板，但是可以用树剖做。
具体地，先离线把树建出来，我们遍历这个时间，不难想到需要统计一个 \(val_x\) 表示 \(x\) 的子树内有多少能到 \(x\)。
记边为 \(x\rightarrow y\)，连边的时候就使用 dsu 找到 \(x\) 最上面的那个点 \(z\)，然后 \(x\sim z\) 的点加上 \(val_y\)。
答案即为 \(val_y(val_z-val_y)\)，只是我降智了想很久才想到这个简单容斥。
使用 BIT 维护即可。