Luogu P3760 [TJOI2017]异或和(01Trie)

题目描述

https://www.luogu.com.cn/problem/P3760

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求所有区间和的异或和

$n\le 10^5,\sum a_i\le 10^6$

Solution

我们要求这个东西 $\bigoplus_{1\le j\le i\le n}s_i-s_{j-1}$

考虑这样一个做法，我们枚举右端点，维护左端点的异或值

那么每次相当于全局加 $1$，求全局异或和，这个东西可以拿 $01Trie$ 来做

时间复杂度为 $O((n+\sum a_i)\log \sum a_i)$

#include <iostream>
#include <cstdio>
#define maxn 100010
#define Maxn 1000010
using namespace std;

int n, a[maxn], s[maxn];

#define lc T[i].ch[0]
#define rc T[i].ch[1]
const int N = 20;
struct Trie {
    int v, sum, ch[2];
} T[Maxn * 21]; int rt = 1, top = 1;
inline void maintain(int i) {
    T[i].v = T[lc].v + T[rc].v;
    T[i].sum = T[lc].sum << 1; 
    T[i].sum ^= T[rc].sum << 1 | T[rc].v & 1; 
} 

void ins(int &i, int v, int o) {
    if (!i) i = ++top;
    if (o == N + 1) return (void) (++T[i].v);
    int d = v >> o & 1; ins(T[i].ch[d], v, o + 1);
    maintain(i); 
} 

void add(int i) {
    if (!i) return ;
    add(rc); swap(lc, rc);
    maintain(i);
}

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i <= n; ++i) {
        for (int j = 1; j <= a[i]; ++j) add(rt);
        ins(rt, 0, 0); ans ^= T[rt].sum;
    } cout << ans << "\n"; 
    return 0;
}