「July」做题笔记 #2

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\) 条。

CF1783G Weighed Tree Radius

[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 维护即可。