APIO2019 题解

T1 奇怪装置

很容易发现，这个东西一定会形成一个环。我们只需要求出环的长度就解决了一切问题。

设环的长度为 (l)。那么从 ((0, 0)) 出发，走 (l) 步一定可以再次回到 ((0, 0))。

也就是说

[left{ egin{align*} & A mid l + lfloor frac lB floor\ & B mid l end{align*} ight. ]

所以 (lfloor frac lB floor = frac lB)。因此设 (x = frac lB)，则 (l = xB)，则 (A mid x(B + 1))。

所以 (x = frac{operatorname{lcm}(A, B + 1)}{A(B + 1)})，(l = xB = frac{operatorname{lcm}(A, B + 1)B}{A(B + 1)})。

有了 (l) 之后就是求区间的并的大小了。这个东西可以直接排序一遍就可以了。

先考虑这样一种做法：

首先如果我们暴力把当前的所有点权大于等于 (w_j) 的边加入并查集，那么这次询问的答案就是 (s_j) 所在并查集的大小。

这样是 (O(Qm)) 的。

想要把这个暴力改的稍微优雅一点可以这样：

先找出所有没有被修改过的边加入并查集。

对于每一次询问，枚举所有修改，对于在它之前最后一次修改这条边的一次修改，如果修改后的权值大于等于 (w_j) 就加入并查集。这里的并查集需要回退。

这样的时间复杂度变成了 (O(mlog m + Q^2log m))。

我们发现，这样做涉及到的边只有询问的边。我们是不是可以每隔几次询问就暴力重构一遍来保证目前没有被重构的询问尽量少呢？这样做可以看成把询问分成很多块。

如果采用这样的策略，那么我们每一次询问只需要遍历这一块内的修改即可。

那么这样的时间复杂度就是 (O(frac{Qmlog m}B + QB))。

当 (B = sqrt{mlog m}) 时最优。

这样的时间复杂度就是 (O(Qsqrt{mlog m}))。

对于每个点 (x) 维护其所在段的右边界 (r_x)。那么从 (a) 能够到达 (b) 当且仅当 (r_a geq b)。

可以用树套树维护 (r_i)。对于一次 toggle 操作，不管是点亮还是熄灭，影响到的 (r_i) 都只有这个区间的修改点 (x) 左边的部分，内容是把它们的 (r) 修改成 (x) 或者从 (x) 修改成一个更大的。

同时，可以发现，一个路段在 (i) 时刻通了，那么它可以带来贡献 (q - i) 的时间。如果在 (j) 时刻断了，那么它带来了 (q - i) 的负贡献。我们只需要维护这个这个东西就可以了。

所以树套树的第一维是 (i)，第二维是 (r_i)，存储的是 (r_i) 变成 (j) 的贡献。但是需要特判的是，如果查询的时候路段处于联通状态，那么需要从总贡献中扣除 (q - now)。

听说还可以用 cdq 分治维护，应该也是差不多的做法了。