这里放传送门
mex这个东西非常讨厌啊,没有办法合并也没有办法前缀和之类的。 但是这个题的话它最多只有n个数,也就是说它的mex值一定在[0..n]这个区间之内。 那么如果我们用分块维护mex的话,可以维护每个块内的数有没有全部出现过,如果没有全部出现过就可以暴力进去找到底是谁没有出现过。 这样的话修改是O(1)的。
修改这么快那就可以跑莫队辣 树上带修莫队。。跟糖果公园那个超级卡评测题的做法是基本上一样的。 树上莫队之类的话可以看一下BZOJ3757苹果树 带修莫队之类的话可以看一下BZOJ2120数颜色 然后就把这些东西拼拼凑凑就出来这个题了= =
莫队这玩意儿复杂度太玄了。。树分块开到
新闻热点
疑难解答