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<