CF1797E

Miraik · 2023-04-11 11:37:49 · 题解

容易想到让 i 向 \varphi(i) 连边，得到一棵树。这个树的高度不高，是 O(\log n) 的。

于是修改操作可以直接暴力，链表维护，跳到根（即变成 1）就从链表中删去就好。

再看询问。找到区间点的 LCA x，则答案即为 \sum_{i=l}^r dep_i - (r-l+1) \times dep_x。

根据经典结论，一堆点的 LCA 即为它们中 dfs 序最小和最大的点的 LCA。当然就算不知道这个，也是可以直接在线段树上暴力维护的（只是会多一个 \log）。

于是线段树维护区间 dfn 的最大最小值，找到 x 就容易了。而 \sum_{i=l}^r dep_i 也很好维护，这些信息直接在修改的时候更新就可以了，树状数组即可。

时间复杂度是 O(n \log n \log V)，瓶颈在于 1 操作。