题解 CF842D 【Vitya and Strange Lesson】

· · 题解

感觉应该是个经典问题，亏我还不知道。

实际上就是询问你集合中的数都异或上某个数的的\text{mex}。

考虑常用的操作异或集合的手段，我的第一反应是线性基，然而线性基只能插入，不能修改，再者她也不能查询\text{mex}这么奇怪的东西。

先不考虑异或，显然\text{mex}是有可二分性的，我们需要一个数据结构支持查询小于某个数的数是否都出现过，然后我们就可以二分了，我的第一反应是值域线段树，显然是可以做的，直接在线段树上二分就可以了，具体来说走到线段树的某个节点时，看一下左儿子存在的数是不是等于左儿子对应的值域大小，即看一下左儿子是不是满的。然而，线段树也不能维护异或这么奇怪的东西。

实际上我们可以选取和线段树结构相同的另一个数据结构（或者说她们就是同一个东西），\text{01trie}。

我们也可以在\text{01trie}上二分查\text{mex}，并且走到\text{trie}上某个点时，如果异或的数这一位为1，意义就是交换\text{trie}的左右儿子，然后就可以用和线段树一样的方法做了。

有一个细节就是，在计算\text{trie}一个点的\text{size}时，注意一个数出现多次只计算一次。

其他具体实现可以看一下代码，还是比较易懂的。

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=3e5+5,Lim=18;

int tr[maxn*19][2],nowxor,cnt=1,siz[maxn*19],n,m;

template<typename T>
inline void read(T &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
    x=c^48;
    while(isdigit(c=getchar())) x=x*10+(c^48);
    x*=f;
}

void insert(int x,int u=1,int now=Lim)
{
    if(now==-1) return siz[u]=1,void();
    int s=x>>now&1;
    if(!tr[u][s]) tr[u][s]=++cnt;
    insert(x,tr[u][s],now-1);
    siz[u]=siz[tr[u][0]]+siz[tr[u][1]];
}

inline int query(int x=nowxor)
{
    int u=1,res=0;
    for(int i=Lim;i>=0;--i)
    {
        int s=x>>i&1;
        if(siz[tr[u][s]]==((1<<i))) u=tr[u][s^1],res|=(1<<i);
        else u=tr[u][s];
        if(!u) return res;
    }
    return res;
}

int main()
{
    int x;
    read(n);read(m);
    for(int i=1;i<=n;++i)
        read(x),insert(x);
    while(m--)
    {
        read(x);nowxor^=x;
        printf("%d\n",query());
    }
    return 0,QAQ;
}