https://codeforces.com/gym/102979

F. Find the XOR

 

题意：给定一张带边权无向图，定义一条路径的长度等于路径上所有边的异或和，定义 d(u,v)d(u,v) 为所有 uu 到 vv 的路径中最长的路径长度（不需要是简单路径），多次询问，每次给定 l,rl,r，问对所有 l≤i<j≤rl\le i<j\le r，d(i,j)d(i,j) 的异或和。

线性基

[WC2011] 最大Xor路径 的增强版

给定 u,vu,v，求 d(u,v)d(u,v) 的方法与WC2011相同，先dfs找出一些环，放进线性基里，任意找一条 u,vu,v 的路径，通过找到与环的最大异或和。

设 D[u]D[u] 表示 uu 到 1 的路径长度，则 d(u,v)=D[u]⊕D[v]⊕Maxd(u,v)=D[u]\oplus D[v]\oplus \text{Max}，其中 Max\text{Max} 为线性基中与 d(u,v)d(u,v) 异或和最大的值。

还有一个很重要的性质：

设 Max(x)Max(x) 表示 xx 与线性基中值异或后取得的最大值，Min(x)Min(x) 表示 xx 与线性基中值异或后取得的最小值。

则有

若 nn 为偶数，则 Max(x1)⊕Max(x2)⊕⋯⊕Max(xn)=Min(x1⊕x2⊕⋯⊕xn)Max(x_1)\oplus Max(x_2)\oplus \cdots\oplus Max(x_n)=Min(x_1\oplus x_2\oplus\cdots\oplus x_n).

若 nn 为奇数，则 Max(x1)⊕Max(x2)⊕⋯⊕Max(xn)=Max(x1⊕x2⊕⋯⊕xn)Max(x_1)\oplus Max(x_2)\oplus \cdots\oplus Max(x_n)=Max(x_1\oplus x_2\oplus\cdots\oplus x_n).

所以就可以先计算所有 D[i]⊕D[j]D[i]\oplus D[j]，再计算考虑线性基后的最大值。而 [l,r][l,r] 中每个点被异或了 r−lr-l 次，所以只要分奇偶讨论即可。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
struct Linear_Basis
{
	int b[63], nb[63], tot, len;	//共len个基，(1ll<<len)个不同的异或和值，包括0

	bool ins(int x)//插入
	{
		for (int i = 30; i >= 0; i--)
			if (x&(1 << i))
			{
				if (!b[i]) { b[i] = x; len++; break; }
				x ^= b[i];
			}
		return x > 0;
	}

	int Max(int res)//所有可能异或中最大
	{
		for (int i = 30; i >= 0; i--)
			res = max(res, res^b[i]);
		return res;
	}

	int Min(int res)//所有可能异或中最小
	{
		for (int i = 30; i >= 0; i--)
			res = min(res, res^b[i]);
		return res;
	}

} LB;
int n, m, q;
struct E
{
	int v, w;
};
vector<E>G[N];
int d[N], vis[N];
void dfs(int u, int _fa) {
	vis[u] = 1;
	for (E& e : G[u]) {
		int v = e.v, w = e.w;
		if (vis[v])LB.ins(d[v] ^ d[u] ^ w);
		else {
			d[v] = (d[u] ^ w);
			dfs(v, u);
		}
	}
}
int sum[N];
int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back({ v,w });
		G[v].push_back({ u,w });
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++)sum[i] = (sum[i - 1] ^ d[i]);
	while (q--) {
		int l, r;
		scanf("%d%d", &l, &r);
		int ans = 0;
		if ((r - l) & 1)ans = (sum[r] ^ sum[l - 1]);
		if (1ll * (r - l + 1)*(r - l) / 2 % 2 == 0) {
			ans = LB.Min(ans);
		}
		else ans = LB.Max(ans);
		printf("%d\n",ans);
	}
	return 0;
}