BZOJ3261：最大异或和——题解

时间：2023-03-08 21:06:56

http://www.lydsy.com/JudgeOnline/problem.php?id=3261

给定一个非负整数序列{a}，初始长度为N。
有M个操作，有以下两种操作类型：
1、A x：添加操作，表示在序列末尾添加一个数x，序列的长度N+1。
2、Q l r x：询问操作，你需要找到一个位置p，满足l<=p<=r，使得：a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。

前置技能：HDU4825

会了这个前置技能之后默认你会如何建trie跑贪心了。

参考：https://www.cnblogs.com/y7070/p/5000471.html

对于一段区间的异或和=r的前缀异或和^l-1的前缀异或和。

所以我们处理出所有前缀异或和完后往trie上插。

不过由于是区间询问，所以按照主席树（可持久化线段树）的想法，我们建立可持久化trie，具体的建立方法大致和主席树差不多，就不多讲了直接看代码吧。

至于询问，我们直接询问哪个前缀能和（n的前缀异或和^x）异或值最大即可。

直接引用参考博客：

如果 x （询问数）的这一位为 p ，那么我们查询Sum[son[l][p ^ 1]] - Sum[son[r][p ^ 1]，Sum为节点上有多少的值。

如若 表达式 > 0 那么我们就像 p ^ 1 的方向行走，同时 答案加上 1 << d 因为这一位被我们错开了。

否则只好向 p 的方向行走， 不加上 1 << d。

原因请参考前置技能。

另外还要注意我们查询的内容本身就是前缀和，左端点和右端点就需要同时减一，同时查区间，那么左端点就还需要需要减一。

参考里提到了一个小技巧就是在最开始插一个0，这样就不需要左端点和右端点同时减一了，不然自己看着怪难受的。

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

typedef long long ll;

const int N=6e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

inline char getc(){

    char ch=getchar();

    while(ch!='A'&&ch!='Q')ch=getchar();

    return ch;

}

struct node{

    int son[],sum;

}tr[*N];

int tot,b[N],rt[N],pool;

void insert(int y,int &x,int k,int now){

    tr[x=++pool]=tr[y];

    tr[x].sum++;

    if(now<)return;

    bool p=k&(<<now);

    insert(tr[y].son[p],tr[x].son[p],k,now-);

    return;

}

int query(int nl,int nr,int k,int now){

    if(now<)return ;

    bool p=k&(<<now);

    int delta=tr[tr[nr].son[p^]].sum-tr[tr[nl].son[p^]].sum;

    if(delta>)return (<<now)+query(tr[nl].son[p^],tr[nr].son[p^],k,now-);

    else return query(tr[nl].son[p],tr[nr].son[p],k,now-);

}

int main(){

    int n=read()+,m=read();

    for(int i=;i<=n;i++)b[i]=b[i-]^read();

    for(int i=;i<=n;i++)insert(rt[i-],rt[i],b[i],);

    for(int i=;i<=m;i++){

    char ch=getc();

    if(ch=='A'){

        b[++n]=b[n-]^read();

        insert(rt[n-],rt[n],b[n],);

    }else{

        int l=read(),r=read(),x=read();

        printf("%d\n",query(rt[l-],rt[r],b[n]^x,));

    }

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

相关文章