解题思路

很巧妙的一道题。我们可以考虑用二维树状数组去做，新建障碍视为在二位数组中对一个矩形区域增加一个值，而移除障碍就是减掉这个值，查询就是判断两个点的值是否一致。

那么问题来了，这个值要加多少呢？这个题给了很巧妙的做法，就是每次随机一个数（可以去 Editorial 看一下证明）。当然其他不会导致重复的生成方式也是可以的。

解题思路

算是一道 Link/Cut Tree 的模板题了，另外也可以巩固一下 Splay 的合并信息的方法。应特别注意 PushDown 相关的计算不要出错。

解题思路

2016 CCPC 长春的一道银牌题，要求强制在线。用过主席树求区间第 K 大以及区间不同数个数的话基本就是一眼题了，比以前不会主席树的时候用的分块做法不知道高到哪里去了。

按照求区间不同数的做法建树，查询时先查出区间内不同数的个数，除以 2 得到一个数 k，用这个 k 在区间 [l, n] 内查询第 k 大即是题目中询问的中位数。

解题思路

本题是要求区间内不同数的个数，这是主席树的常见应用之一了。

做法很简单，我们可以倒序（从右向左）建立主席树，如果一个值还没出现过，则直接插入，否则删除后再重新插入（相当于保留这个数最左出现的位置）。之后要查询 [l, r] 时，选用 l 位置的主席树，这时树中的数据是 [l, n] 范围内的，因此查询时需要传入 r 作为挡板，仅统计小于等于 r 的个数，这样就可以实现 [l, r] 区间不同数的查询。

当然也可以保留每个数最右出现的位置来正序建树，和上面的做法就反过来了。

解题思路

主席树的区间第 K 大的树上版本。

从根结点到每个结点都建立一个版本的线段树即可。查询时 a 到 b 路径时需要按照 $root[a] + root[b] - root[lca(a,b)] - root[fa[lca(a,b)]]$ 计算。