Chlience

【题解】BZOJ 3261 最大异或和
Problem给定一个非负整数序列,初始长度为 $n$有 $m$ 个操作,两种操作类型A x:在序列末尾添加一个 ...
扫描右侧二维码阅读全文
21
2018/12

【题解】BZOJ 3261 最大异或和

Problem

给定一个非负整数序列,初始长度为 $n$

有 $m$ 个操作,两种操作类型

  1. A x:在序列末尾添加一个 $x$
  2. Q l r x:寻找一个位置 $l\leq p\leq r$ 使得 $a[p]\ xor\ a[p+1]\ xor\ \cdots\ xor \ a[n]\ xor\ x$ 最大

Thought

因为是一个后缀异或和,那么先考虑有一个异或和 $y=a[1]\ xor\ \cdots\ xor\ a[n]\ xor\ x$,就可以将后缀异或和转化为找到到一个位置 $l-1\leq p \leq r-1$ 使得位置 $p$ 的前缀异或和 $xor\ y$ 最大

异或和最大值自然而然想到 $Trie$ 树,而又因为要查询区间异或和最大值,所以需要可持久化。利用主席树维护,提取区间并按照 $Trie$ 树的方式求最大值即可

几个值得注意的点:

  1. 需要先加入一个为 $0$ 的值,因为初始异或和为 $0$
  2. 考虑好应该选择的区间到底是哪一段

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 600010;
const int M = 20000010;
int rt[N];
int L , R , ANS;
int n , m;
int x0r;
char opt[11];
struct Tree {
    int ch[M][2];
    int siz[M];
    int cnt;
    void insert(int& x , int l , int r , int num) {
        ++ cnt;
        ch[cnt][0] = ch[x][0]; ch[cnt][1] = ch[x][1];
        siz[cnt] = siz[x] + 1;
        x = cnt;
        if(l > r) return;
        bool w = num & (1 << (r - l));
        insert(ch[x][w] , l + 1 , r , num);
    }
    void query(int l , int r , int num) {
        if(l > r || !R) return;
        bool w = num & (1 << (r - l));
        if(siz[ch[R][w ^ 1]] - siz[ch[L][w ^ 1]]) {
            ANS += (1 << (r - l));
            L = ch[L][w ^ 1];
            R = ch[R][w ^ 1];
        }
        else {
            L = ch[L][w];
            R = ch[R][w];
        }
        query(l + 1 , r , num);
    }
}t;
int main() {
    n = read(); m = read();
    t.insert(rt[1] , 0 , 30 , 0);
    for(int i = 1 ; i <= n ; ++ i) {
        x0r ^= read();
        rt[i + 1] = rt[i];
        t.insert(rt[i + 1] , 0 , 30 , x0r);
    }
    for(int i = 1 ; i <= m ; ++ i) {
        scanf("%s" , opt);
        if(opt[0] == 'A') {
            x0r ^= read();
            rt[n + 2] = rt[n + 1]; ++ n;
            t.insert(rt[n + 1] , 0 , 30 , x0r);
        }
        else {
            L = rt[read() - 1]; R = rt[read()];
            int num = read() ^ x0r;
            t.query(0 , 30 , num);
            printf("%d\n" , ANS);
            ANS = 0;
        }
    }
    return 0;
}
Last modification:December 21st, 2018 at 09:07 pm

Leave a Comment