01ディクショナリツリーの相違または最大値と最小値テンプレート(削除付き)

2021 ワード

異或いは最小値を求めるテンプレート
#include   
using namespace std;  
const int maxn=300005;  
int n,m;  
int a[maxn],b[maxn];  
int ch[30*maxn][2];  
int val[30*maxn];  
int sz;  
void insert(int num){  
    int u=0;  
    for(int i=29;i>=0;i--){  
        int c=((num>>i)&1);
        if(!ch[u][c]){  
            ch[u][c]=++sz;  
        }  
        u=ch[u][c]; 
        val[u]++;  
    }  
}  
 void remove(int num)
 {
 	int u=0;
 	for(int i=29;i>=0;i--)
 	{
 		int c=((num>>i)&1);
 		int pre = u;
 		u = ch[u][c];
 		if(--val[u]==0) ch[pre][c]=0;
 	}
 }
  
int query(int num){  
    int p=0,v=0;
    for(int i=29;i>=0;i--)
    {
    	int c=((num>>i)&1);
    	if(ch[p][c])p=ch[p][c];
    	else 
    	{
    		p=ch[p][c^1];
    		v+=(1<

最大値を求めるテンプレート:
#include  
using namespace std;  
#define Memset(x, a) memset(x, a, sizeof(x))   
#define _for(i,a,b) for(int i=a;i<=b;i++)
const int maxn = 600007;//          
int ch[32*maxn][2];         //        
long long val[32*maxn];            //        
long long a[maxn];
int sz,q,n;                     //          
long long num;  
  
void init(){  
    Memset(ch[0],0);           //     
    sz=1;  
}  
  
void _insert(long long a){  
    int u=0;  
    for(int i=32;i>=0;i--){  
        int c=((a>>i)&1);  
        if(!ch[u][c]){  
            Memset(ch[sz],0);  
            ch[u][c]=sz++;  
        }  
        u=ch[u][c];  
        ++val[u];  
    }  
}  
  
void _delete(long long a){  
  int u=0;  
  for (int i=32; i>=0; --i){  
      int c=((a>>i)&1);  
      u=ch[u][c];  
      --val[u];  
  }  
}  
  
long long query(long long a){     
    int u=0;  
    long long ans=0;  
    for(int i=32;i>=0;i--){  
        int c=((a>>i)&1);  
        if (c==1){  
            if (ch[u][0] && val[ch[u][0]]){  
                ans+=1<