01字典树模板

int ch[32*MAX][2]; LL val[32*MAX]; int num[32*MAX]; int sz; LL b[MAX]; void init(){ mem(ch[0]); sz=1; } void inser(LL a){ int u=0; for(int i=32;i>=0;i--){ int c=((a>>i)&1); if(!ch[u][c]){ mem(ch[sz]); val[sz]=0; num[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; num[u]++; } val[u]=a; } void update(LL a,int d){ int u=0; for(int i=32;i>=0;i--){ int c=((a>>i)&1); u=ch[u][c]; num[u]+=d; } } LL query(LL a){ int u=0; for(int i=32;i>=0;i--){ int c=((a>>i)&1); if(ch[u][c^1]&&num[ch[u][c^1]]) u=ch[u][c^1]; else u=ch[u][c]; } return a^val[u]; } const int MAXN = 1E5 + 5; int bits[50]; struct Trie { int data; Trie* child[2]; Trie() { data = 0; memset(child, 0, sizeof(child)); } } *root; void Insert(int num) { Trie* p = root; for (int i = 31; i >= 0; --i) { bool temp = bits[i] & num; if (p->child[temp] == NULL) { p->child[temp] = new Trie; } p = p->child[temp]; } p->data = num; } int Find(int num) { Trie* p = root; for (int i = 31; i >= 0; --i) { bool temp = bits[i] & num; if (p->child[!temp]) { p = p->child[!temp]; } else { p = p->child[temp]; } } return p->data; } void Delete(Trie* p) { for (int i = 0; i <= 1; ++i) { if (p->child[i]) Delete(p->child[i]); } delete p; } int bits[50]; for (int i = 0; i < 32; ++i) { bits[i] = 1 << i; } root = new Trie; Delete(root); #include <unordered_map> unordered_map<int,int> data[30]; void update(int v, int c){//v是数，c取1 -1，1为加，-1为删。 for(int i = 0; i < 30; i++) data[i][v>>i] += c;} int query(int x){ int cur = 0; for(int i = 29; i >= 0; i--){ cur ^= (1<<i) ^ ((1<<i)&x); if(data[i][cur>>i] == 0)cur ^= (1<<i); } return cur ^ x;} int query(int a)//统计>m的个数。 { int u=0; int ans=0; for(int i=22; i>=0; i--) { int c=((a>>i)&1); int cc=((m>>i)&1); if(cc) { if(!ch[u][c^1]) return ans; u=ch[u][c^1]; } else { if(ch[u][c^1]) ans+=num[ch[u][c^1]]; if(!ch[u][c]) return ans; u=ch[u][c]; } } return ans+num[u]; }