ZR#956 集合

待我称王封你为后i 2024-04-20 10:31 62阅读 0赞

##  ##

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

转载于:https://www.cnblogs.com/Repulser/p/11455713.html