DDOSvoid's Blog

2020-2021 Winter Petrozavodsk Camp, Day 9 Contest (XXI Open Cup, Grand Prix of Suwon) F Find the XOR

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/gym/102979/problem/F

Solution

首先我们将所有的环拿出来扔到线形基里，然后随便跑一棵生成树

令 $dis[i]$ 为前缀异或和，$mx(v)$ 表示 $v$ 与线性基异或的最大值，$mn(v)$ 表示 $v$ 与线性基异或的最小值

然后我们有

那么 $d(i,j)=mx(dis[i]\oplus dis[j])$，我们所求为 $\bigoplus_{l\le i<j\le r}d(i,j)$

注意到当 $r-l\equiv 1(\bmod 2)$ 时，$mx$ 括号里面的那个东西为 $D[r]\oplus D[l-1]$，其中 $D$ 为 $dis$ 的前缀和

否则为 $0$

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
#include <iostream>
#define maxn 100010
using namespace std;

int n, m, q; 

struct LinearBasis {
    static const int n = 30;
    
    int a[n + 1];

    void insert(int v) {
        for (int i = n; ~i; --i) {
            if (!(v >> i & 1)) continue;
            if (!a[i]) { a[i] = v; break; }
            v ^= a[i];
        }
    }

    int get_max(int v = 0) {
        for (int i = n; ~i; --i) v = max(v, v ^ a[i]);
        return v; 
    }

    int get_min(int v) {
        for (int i = n; ~i; --i) v = min(v, v ^ a[i]);
        return v; 
    }
    
} S; 

struct Edge {
    int to, next, w;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w; 
    e[c1].next = head[u]; head[u] = c1++;
}

int dis[maxn], D[maxn]; bool vis[maxn];
void dfs(int u, int fa) {
    vis[u] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (v == fa) continue;
        if (vis[v]) { S.insert(dis[u] ^ dis[v] ^ w); continue; } 
        dis[v] = dis[u] ^ w; dfs(v, u); 
    } 
} 


int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add_edge(x, y, z); add_edge(y, x, z); 
    } dfs(1, 0);
    for (int i = 1; i <= n; ++i) D[i] = D[i - 1] ^ dis[i]; 
    for (int i = 1; i <= q; ++i) {
        int l, r, v; cin >> l >> r;
        v = D[r] ^ D[l - 1];
        if ((r - l) % 2 == 0) v = 0;
        if (1ll * (r - l + 1) * (r - l) / 2 & 1) cout << S.get_max(v) << "\n";
        else cout << S.get_min(v) << "\n"; 
    } 
    return 0;
}