2137

神奇的分块。 假如没有 $2$ 操作，我们可以直接用主席树解决。 我们考虑将询问分块，每遍历完一块就将这一块内出现的所有修改更新。如果在块内，就把当前块之前的所有修改暴力算，当然只有修改的节点在询问的节点的子树内才会发生。 具体的来说，我们可以用分块维护 dfs 序，并将块内的元素排序，询问 $O( ......