ZR#956 集合

解法：

维护一个异或操作的懒标记，并对应的处理插入、删除和异或操作。接下来考虑如何整体加一。

考虑一个数字 $ x $ 变为 $ (x+1) \pmod {2^{30}} $ 的过程，设 $ x $ 在二进制表示下从低位到高位依次为 $ a_1,a_2,a_3 \cdots a_{30} $ ，那么我们可以找一个最小的 $ i $ ，值得 $ a_1=a_2= \cdots = a{i-1}=1 $ ，且 $ a_i=0 $ ，然后将 $ a_1,a_2,a_3 \cdots a_i $ 的值翻转。如果不存在这样的 $ i $ 那么我们认为 $ i = 31 $ ，此时要把全1变成全0。

然后我们考虑使用 $ trie树 $ 解决问题，翻转操作对应交换左右儿子操作。

时间复杂度 $ O((n+q)\log_2a_i) $

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

const int N = 2e5 + 5;

const int INF = (1 << 30) - 1;

int num[N >> 5],trie[N >> 5][2];

int q,ans[N >> 5],tot,cnt,s[N],n,tag;

inline void build(int x,int z) {

    int u = 0;

    for(int i = 0 ; i < 30 ; i++) {

        int v = (x >> i) & 1;

        if(!trie[u][v])

            trie[u][v] = ++cnt;

        u = trie[u][v];

    }

    num[u] += z;

}

void work() {

    int u = 0,Cnt = 0;

    int res = ((1 << 30) - 1) ^ tag;

    for(int i = 0 ; i < 30 ; i++) {

        s[++Cnt] = u;

		int v = (res >> i) & 1;

		if(!trie[u][v]) break;

		u = trie[u][v];

    }

    for(int i = 1 ; i <= Cnt ; i++)

        swap(trie[s[i]][0],trie[s[i]][1]);

}//v是前缀路径上的所代表的值

void dfs(int u,int v,int depth) {

	if(depth == 30) {

		for(int i = 1 ; i <= num[u] ; i++)

            ans[++tot] = v ^ tag;

		return;

	}

	if(trie[u][0]) dfs(trie[u][0],v,depth+1);

	if(trie[u][1]) dfs(trie[u][1],v|(1<<depth),depth+1);

	return;

}

int main() {

    scanf("%d%d",&n,&q);

    for(int i = 1 ; i <= n ; i++) {

        int x;

        scanf("%d",&x);

        build(x,1);

    }

    while(q--) {

        int opt,x;

        scanf("%d",&opt);

        if(opt == 1) {

            scanf("%d",&x);

            build(x ^ tag,1);

        } else if(opt == 2) {

            scanf("%d",&x);

            build(x ^ tag,-1);

        } else if(opt == 3) work();

        else if(opt == 4) {

            scanf("%d",&x);

            tag ^= x;

        }

    }

    dfs(0,0,0);

    sort(ans+1,ans+tot+1);

    for(int i = 1 ; i <= tot ; i++)

        printf("%d ",ans[i]);

    //system("pause");

    return 0;

}

巴特西

ZR#956 集合

ZR#956 集合

解法：

CODE:

最新文章

热门文章