欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ3261: 最大异或和(可持久化trie树)

程序员文章站 2022-04-06 11:59:01
题意 "题目链接" Sol 设$sum[i]$表示$1 i$的异或和 首先把每个询问的$x \oplus sum[n]$就变成了询问前缀最大值 可持久化Trie树维护前缀xor,建树的时候维护一下每个节点被遍历了多少次 注意设置好偏移量,不然询问区间为$[1, 1]$的时候可能挂掉 cpp incl ......

题意

题目链接

sol

设$sum[i]$表示$1 - i$的异或和

首先把每个询问的$x \oplus sum[n]$就变成了询问前缀最大值

可持久化trie树维护前缀xor,建树的时候维护一下每个节点被遍历了多少次

注意设置好偏移量,不然询问区间为$[1, 1]$的时候可能挂掉

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, a[maxn], sum[maxn], cnt[maxn * 25], ch[maxn * 25][2], tot, root[maxn];
void insert(int i, int x) {
    x = (sum[i] = sum[i - 1] ^ x);
    int p = root[i - 1], now = (root[i] = ++tot);
    for(int i = 23; i >= 0; i--) {
        bool nxt = x >> i & 1;
        ch[now][nxt ^ 1] = ch[p][nxt ^ 1];
        now = ch[now][nxt] = ++tot; p = ch[p][nxt];
        cnt[now] = cnt[p] + 1;
    }
}
int query(int l, int r, int x) {
    r = root[r], l = root[l];
    int ans = 0;
    for(int i = 23; i >= 0; i--) {
        int nxt = x >> i & 1;
        if(cnt[ch[r][nxt ^ 1]] - cnt[ch[l][nxt ^ 1]] > 0) ans += 1 << i, r = ch[r][nxt ^ 1], l = ch[l][nxt ^ 1];
        else r = ch[r][nxt], l = ch[l][nxt];
    }
    return ans;
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) a[i] = read(), insert(i, a[i]);
    char ss[4];
    for(int i = 1; i <= m; i++) {
        scanf("%s", ss + 1);
        if(ss[1] == 'a') 
            n++, a[n] = read(), insert(n, a[n]);
        else {
            int l = read() - 1, r = read() - 1, val = read();
            printf("%d\n", query(l - 1, r, val ^ sum[n]));
        }
    }
}
/*
5 5
2 6 4 3 6
a 1 
q 3 5 4 
a 4 
q 5 7 0 
q 3 6 6 
*/

上一篇: python 进程

下一篇: 模拟服务器