10.26

数组不要开在局部！！！！！

注意清空！！！！

A

比较简单，考虑到每一次会变成自己的子集，最多只会操作log次，于是预处理初每次操作的位置即可。

B

首先，连通性不会变。然后，同一连通块内，两点距离不超过2。然后考虑题目中的性质，其实相当于可以把一条长度为奇数的路径压成一条边，所以只要两个点之间存在奇数长度的路径，则可以一步到达。

如果连通块内有奇环，则一定存在长度为奇数的路径，否则是个二分图，在同一边的距离为2，不同边的距离为1。

C

对于一次博弈，如果存在一堆石头有奇数个，则先手必胜，否则后手必胜。

证明：如果全是偶数，那么后手可以复制先手的操作，使得每次剩下的都是偶数，于是后手必胜。如果存在奇数，则先手把奇数的取完，则只剩偶数，它就必胜了。

然后考虑统计满足条件的矩形有几个:

对每一行做01前缀和，先枚举矩形上边界，再枚举左右边界，其可满足条件的下边界个数就是这两列的前缀和lcp。暴力做可以把每一列的都拿出来建trie，在trie上统计lcp。

然后枚举上边界，每次上边界增大，就是删除每个串的第一个字符，在trie上就是把根节点的左右子树合并，然后trie合并复杂度显然正确，最后复杂度O(nm）。

D

分析性质题，考虑题面给定的“超现实树”满足什么性质，不难发现，一颗超现实树的右子树一定也是超现实树。于是可以在此基础上dp。

相当于每次在右子树的基础上加上根节点和左子树，其实就是把右子树的左子树拷贝一份放在左边，然后再加上一些叶子。然后可以列出5维dp，貌似状态数量很多，但是有效状态很少，用个map记录转移就过了。