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

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

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

2022-12-19 15:23:10 来源：博客园

【资料图】

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

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

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

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

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

关键词：时间复杂度不能保证美好的每一天

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

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