题目背景来自于 Codeforces 的 rating 四人组。
可以发现答案是由连续的一段或两段 $k$ 次方和组成的。由于 $1 \leq k \leq 50$, 可以直接 $O(nk)$ 预处理，然后每个询问找出最近公共祖先，使用单次 $O(\log n)$ 的算法即可通过。代码难度和思维难度都很小，现场有接近一半的选手 AC 了这个题目。
原本这个题目是有树形态修改的操作的，但感觉这样一来这场比赛对刚接触省选的选手就太不友好了，就改成了一个 NOIP 难度题。
首先很容易注意到一个区间能否重排成 $3$ 的倍数只与其中 $0$ 和 $1$ 的个数有关。
如果其中有偶数个 $1$ ，那么将所有 $0$ 放于高位，这个数就是 $2$ 的偶数幂次减一，是 $3$ 的倍数；如果其中只有一个 $1$，那么总是一个 $2$ 的幂次，无法排列成 $3$ 的倍数。如果有奇数个 $1$ 且没有 $0$ , 是 $2$ 的奇数幂次减一，不是 $3$ 的倍数；有奇数个 $1$ 且只有一个 $0$ , 是 $2$ 的偶数幂次减一再减去一个$2$ 的幂次，不是 $3$ 的倍数；如果有至少三个 $1$ 且有至少两个 $0$，可以组成 $10101_{(2)}$，然后将所有其余 $1$ 放到低位，所有其余 $0$ 放到高位，形成 $3$ 的倍数。综上，不能重排的情况只有两种： 奇数个 $1$ 和不超过一个 $0$，只有一个 $1$。观察到这些区间要么只有一个 $1$ 要么只有一个 $0$ 用两个set维护所有 $0$ 和 $1$ 的位置然后查询前驱后继，用树状数组维护即可，复杂度 $O(n\log n)$（认为 $m$ 和 $n$ 同阶）。这个题目现场每个部分分都有不少人，有五六个高水平的选手 AC 了，是比赛的主要区分度题。
我们现在把自己当做 master，考虑如何构造集合卡掉 pupil。
明显只要所有点的集合相同就能卡掉不是二分图的情况，而且不同的连通块互不影响，度不超过 $1$ 的节点也可以去掉。所以现在我们只考虑所有节点均有至少两条边的二分图。
对于完全二分图 $K_{3,3}$, 样例已经给出了构造；对于完全二分图 $K_{2,4}$，只要一边是 $(A,B)$ 和 $(C,D)$，另一边是 $(A,C)$ ，$(A,D)$，$(B,C)$，$(B,D)$ 即可。然后如果图中有两个偶环有不超过一个公共点，可以使用一个限制偶环点染色的方法卡掉，即一个点是 $(A,B)$，与它相邻的两个是 $(A,C)$ 和 $(C,B)$ ,这样之后的点就不能染 $C$ 了。
现在我们的图只有两种情况了：偶环和两个度为 $3$ 的节点，其中有三条不相交的路径。对于偶环，如果其中两个相邻节点的集合不同，则可以一个节点染一个另一个集合没有的颜色，然后顺着环染即可，所以答案为 YES；三条不相交的路径，只有长度为 $ 2-2- $ 偶数才为 YES，因为对于 $ 2-4-4,1-3-3$ 均有卡掉的方法，而如果相邻两个度为 $ 2 $ 的节点，可以他们和某一边选相同的颜色集合，这样颜色交替变化，相交部分还是相同的。
现在我们只需要使用类似最短路或类似拓扑排序的方法去掉度不超过 $1$ 的节点，然后对每个联通分量判断是否是偶环或 $ 2-2- $ 偶数即可。复杂度 $O(m)$。
这个题目现场有一个人使用奇怪的双连通分量方法 AC 了本题，另有人判断了一部分情况获得了 60 分，少数人写了 20 分暴力，大部分人写了 10 分的判断二分图。
鄂公网安备 42010202000505 号