codeforces842D

题目链接 :

                                点击打开链接

题意:给n个数(n<=3e5), 给出q次询问,此次询问这n个数字^x后的mex值(最小没出现的值)。

思路:建字典树,n^x^y == n^(x^y)  所以不用每次都修改树,只需要累计起来就好,具体细节再想一想就好(注意:去重)


#include
using namespace std;

const int maxn = 1e6 +100 ;
int n,q,x,m;
bool vis[maxn];
int  cnt[maxn];
int tot;
int nt[maxn][10];

int newnode()
{
    memset(nt[tot], 0, sizeof(nt[tot]));
    cnt[tot] = 0;
    return tot++;
}

void Insert(int x, int fa)
{
    for(int i = 20; i >= 0; i--)
    {
        int ans = (x>>i)&1;
        if(!nt[fa][ans])
        nt[fa][ans]=newnode();
        cnt[nt[fa][ans]]++;
        fa = nt[fa][ans];
    }
}

int query(int x, int fa)
{
    int val = 0;
    for(int i = 20; i >= 0; i--)
    {
        int ans = (x>>i)&1;
        if(!nt[fa][ans])  return val;
        if(cnt[nt[fa][ans]] == (1<


 

你可能感兴趣的