luogu4563

题目描述

给定一个序列。对于一个点，能覆盖另一个点的条件是且对于任意，都有。问所有的区间，每个区间的最小覆盖数异或和是多少。

解题思路

首先我们知道，对于任意一个区间，其右端点是必须要选的。

假设和为能覆盖的点序列中的相邻两点，并且且。那么我们可以发现这一点无法被覆盖，因此我们需要一个新的节点来覆盖它。

那么这一部分是否具有局部性呢？我们考察对是否有贡献。连接、，可以发现和都在直线的下方，并且它们被点分割。因此不存在能绕过到达的直线。因此对毫无贡献。因此具有局部性。

那么我们就可以考虑动态规划。记表示右端点为，左端点为的区间的答案。记上一个可以被覆盖的点为。倒叙枚举，当可以覆盖时，；当不可以覆盖时，。

时间复杂度。