XUANMING'S JOURNAL屏幕在深夜微微发亮,我心在远方。
← 回到笔记
FIELD NOTES

题解 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;
}

输入关键词,搜索全部笔记。