洛谷 P6580 [Ynoi 2019] 美好的每一天~ 不连续的存在 题解

既然是YNOI那肯定是要分块的。先考虑树是一条链的情况，可以直接回滚莫队，对n个节点组成的序列分块。在回滚莫队的过程中，当前维护的区间一共会扩展(O(nsqrt n))次，每次都是合并了恰好2个连通块。可以用线段树合并对每个连通块维护其中颜色的奇偶性。注意到每次合并，都有其中一个连通块的大小是1，这就保证了复杂度，(O(nsqrt nlogn))。

然后再来看树不是链的情况。这是再用上面的方法复杂度就假了，因为这时加入一个点可能会合并不止一个连通块。对所有边组成的序列分块也不行，因为线段树合并和撤销的复杂度不能保证。那我们应该对其他什么东西分块才对。

考虑这样一件事情：把节点1~n从左到右排成一行，然后从右到左一个个把节点加入维护的区间，并进行连通块之间的线段树合并。令(c_i)表示加入第i个点时，线段树合并内部进行的操作次数。线段树合并的时候不是要递归吗，每次递归都算一次操作。显然，(sum{c_i}=O(nlogn))。接下来用数组c对1-n组成的序列进行"加权"然后分块跑莫队，也就是把i号点复制(c_i)份，形成一个长度(O(nlogn))的序列，然后对它回滚莫队。这时候发现复杂度就对了，不会出现不均匀的情况。

线段树合并常数太大了，考虑使用压位trie。也就是一个类似这样的结构：

时间复杂度还是(O(nsqrt nlogn))级别的，常数小了不少。