比赛链接：https://qoj.ac/contest/1009

开局我看了 C ，但是感觉没有好写的写法，润了，感觉是签到，相信队友（主要当时在吃早餐，会了也写不了，但其实这个时候应该和队友说一下，还是太过相信队友了，虽然队友确实值得信任）。

后面队长看了，说 SB 题，写了，虽然后面听说他一开始的做法烦了，后面改成好写的在 15 min 一发过了。

F 和队友讨论，是 SB 题，上去写，过了。

K 我声称结论是异或和等于 $0$ ，和队友说了结论的证明，队友觉得没问题，但我不会计数，伟大的队长说是莫队，我一听，很对，然后上去写，WA 了，后面想了想证明，假麻了，我应该知道队友大部分时候是没认真听证明的。

接着队友非常给力的过了 J,G ，此时一个小时。

然后和队友接着讨论 K ，注意到三堆石头一定有解，四堆和 $-1$ 异或有关，这个时候就非常疑惑了。

三堆石头一定有解说明不是像 NIM 游戏那样纯粹的算式判定，但四堆石头的结论否定了这一点。

于是我们猜测跟奇偶性有关，但是我这个时候非常唐氏的搞了个 $5$ 堆先手无法直接操作到 $4$ 堆的例子，然后说这是不对的。

于是队友上去写了个暴力，发现 $5$ 堆没有反例，我发现反例我少考虑了个情况，于是觉得结论应该是对的，遂上机，过了。此时一个小时四十分钟，进入坐牢时间。

然后队长开 B ，我开 L ，Imakf 上机写 A ，Imakf 声称是讨论 + 插值。

然后一路写 + 调到三个小时才过，期间我和他讨论，但貌似是倒忙，因为我的声称是让他换题，原因是：为什么能插值，我们不知道，你讨论全了没，我们不知道，那没有写对的道理，况且有几道看上去能做的题目，所以我想让他下来做其他可做题。

最后过了，上 A 就是正确的，但是没过吗，也没有错，错在我帮不上忙，毕竟平时这种事是队长和他干的，我对这种题目一点想法都没有，为什么是插值不知道，为什么讨论全了不知道，Imakf 伟大，无需多言。

期间我 L 声称了一个做法，然后上去写，三个半小时 RE 了，发现做法又假了，后面下去吃饭，发现可以流，上去写在四个小时四十分钟过了。

Imakf 非常厉害的在四个小时 20 分钟的时候过了 E 。、

赛后 Imakf 声称 L 一看就可以流，但是他没说，这就是他的问题了，如果是假的，吹牛逼该罚，如果是真的，不说，该罚。

最后队长上机 B ，可惜因为我们队的唐氏儿本场比赛从头演到尾吃掉队长机时，导致队长最后遗憾离场。

细数这场我的罪孽，K,L 假做法吃掉大量机时，以后上机前麻烦认真想想自己的做法，不要假了，假了就炸了。

部分题解：

C

只要不出现一个数字出现 $n$ 次就可以，做法是把所有出现过的数字轮换一下填入。

F

显然 $x,k-x$ 处于一个等价类，相邻两个数字是等价类就可以删。

则做法为能删就删，

K

判断方法为：奇数先手必胜，偶数则所有数字 $-1$ 异或起来不为 $0$ 则必胜。

证明：

不妨考虑归纳，首先一堆是对的，现在假设 $k-1$ 堆是对的。

假设 $k$ 是偶数，那么显然是对的，因为谁先变成 $k-1$ 谁输，故是 $a_{i}-1$ 的 NIM 游戏，谁最先操作最后一个谁输。

假设 $k$ 是奇数，考虑先把所有数字减 $1$ ，即现在 $a_{i}\ge 0$ ，设异或起来为 $x$。

我们不妨证明以下两个情况的其中一个一定会发生：

  1. 我们能找到 $i≠j$ ，满足：$min(a_{i},a_{j})\le x\bigoplus a_{i}\bigoplus a_{j}\le a_{i}+a_{j}$ 。
  2. 我们能找到 $i$ ，满足：$a_{i}\bigoplus x=0$ 。

首先有几个性质：

  1. $x\bigoplus y\le x+y$
  2. 若 $y$ 的二进制最高位在 $x$ 中为 $0$ ，则 $x\bigoplus y \ge x$ ，如果为 $1$ ，则 $x\bigoplus y \le x$

然后讨论一下：

  1. $x=0$ ，随便取一个数字 $a_{i}$ ，否则取在 $x$ 最高位为 $1$ 的 $a_{i}$ ，简而言之，我们希望：$x\bigoplus a_{i} \le a_{i}$ 。
  2. 然后若 $x\bigoplus a_{i}=0$ ，则符合情况 $2$ ，否则找到在 $x\bigoplus a_{i}$ 最高位为 $0$ 的 $a_{j}(j≠i)$ ，故有：$x\bigoplus a_{i}\bigoplus a_{j} \le x\bigoplus a_{i} + a_{j} \le a_{i} + a_{j}$ ，同时有 $x\bigoplus a_{i}\bigoplus a_{j}\ge a_{j}$ ，综上，满足情况 $1$ 。

证毕。

显然这两个条件满足其中一个都可以直接导出 $k-1$ 的先手必败态，所以先手必胜，证毕。

思考过程就是手玩，发现 $3,4$ 堆的必胜条件后，去猜结论，然后证明出来就对了。虽然我们压根没证明，写暴力发现 5 堆也是对的就直接写了

$3$ 堆必胜的证明还是挺简单的，就是拿出最大的堆，留下剩下两堆差值的石头，然后和最小的堆合并，就可以剩下两个大小一样的堆，这样先手就必胜了。

在得到这个结论之后，莫队一下就做完了，时间复杂度：$O(n\sqrt{m})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const int V = 2e6 + 5;
const int B = 300;
struct node{
	int l, r, id;
}op[N];
int a[N], n, q;
int be[N];
int cnt[V][2], zcnt[2];
LL ans = 0ll;
void ins(int x, int t){
	zcnt[t]++;
	ans += cnt[x][t];
	cnt[x][t]++;
}
void del(int x, int t){
	zcnt[t]--;
	cnt[x][t]--;
	ans -= cnt[x][t];
}
LL zans[N];
int main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i]--;
		a[i] ^= a[i - 1];
	}
	for(int i = 0; i <= n; i++){
		be[i] = i / B + 1;
	}
	for(int i = 1; i <= q; i++){
		cin >> op[i].l >> op[i].r;
		op[i].l--;
		op[i].id = i;
	}
	sort(op + 1, op + q + 1, [](node x, node y){
		return be[x.l] == be[y.l] ? x.r < y.r : x.l < y.l;
	});
	int l = 1, r = 0;
	for(int i = 1; i <= q; i++){
		auto [ll, rr, id] = op[i];
		while(r < rr){
			r++;
			ins(a[r], r & 1);
		}
		while(l > ll){
			l--;
			ins(a[l], l & 1);
		}
		while(r > rr){
			del(a[r], r & 1);
			r--;
		}
		while(l < ll){
			del(a[l], l & 1);
			l++;
		}
		zans[id] = 1ll * (rr - ll + 1) * (rr - ll) / 2 - ans;
	}
	for(int i = 1; i <= q; i++) cout << zans[i] << "\n";
	return 0;
}

L

显然，必要条件是最大边和最小边在一个边双上。

所以不妨猜测边双上的最大差值就是答案。

但是怎么证明这个事情呢？

边双有个很好的性质：割掉一条边不会影响连通性，那么什么东西和连通性有关呢？就是最小割。

这么考虑这个问题：

现在指定两条边，怎么确定性的构造一个环经过这两条边呢？考虑把这两条边删掉，以这两天边的两个端点分别作为起终点，只需要证明这个图的割 $> 1$ 就行了，一个比较有疑惑性的事情是，我们其实已经删掉了两条边，所以会不会不满足割的性质，但由于我们求最小割实际上考虑的是这四个点之间的连通性，所以其实等价于没有删除。

证明：我们假设被割的边是 $(x,y)$ ，显然 $x,y$ 不会是网络流图中的 $st,ed$ ，考虑边双中这个边被割掉后，这四个点一定有两个点不依赖于这两条边联通，所以网络流上仍然是联通的，矛盾，证毕。

具体来说，设一条边为 $(l_1,l_2),(r_1,r_2)$ ，求 $l_{1},l_{2}$ 到 $r_{1},r_{2}$ 的最近点对，显然 $(l_1,l_2),(r_1,r_2)$ 不会在这条路径上，否则与最近点对矛盾。

然后跑网络流就行了。

时间复杂度：$O(n)$ 。

至于退流，由于边权为 $1$ ，所以直接退就是对的吗？