字典树
struct Trie
{
struct node
{
int nex[27];ll pfx,wd;
void clear(){mem(nex,0);pfx=wd=0;}
}t[1000000];
struct memory
{
static const int __=1e5+5;
int idx,trash[__];
int get()
{
if(trash[0])return trash[trash[0]--];
return ++idx;
}
void del(int x){trash[++trash[0]]=x;}
void clear(){idx=trash[0]=0;}
}M;
Trie() {M.clear();t[0].clear();}
int get_idx(char *s)
{
int x=0;
for(int i=1;s[i];i++)
{
int k=s[i]-'a'+1;
if(!t[x].nex[k])return -1;
x=t[x].nex[k];
}
return x;
}
int insert(char *s,ll val,bool prefix=false)
{
int x=0;
for(int i=1;s[i];i++)
{
int k=s[i]-'a'+1;
if(!t[x].nex[k])
{
int idx=M.get();
t[x].nex[k]=idx;
t[idx].clear();
t[idx].nex[0]=x;
}
x=t[x].nex[k];
t[x].pfx+=val;
}
if(!prefix)t[x].wd+=val;
return x;
}
void erase(char *s,ll val,bool prefix=false)
{
int x=0,i;
for(i=1;s[i];i++)
{
x=t[x].nex[s[i]-'a'+1];
t[x].pfx-=val;
}
if(!prefix)t[x].wd-=val;
for(--i;x && !t[x].pfx;i--)
{
M.del(x),x=t[x].nex[0];
t[x].nex[s[i]-'a'+1]=0;
}
}
ll search(char *s,bool prefix=false)
{
int x=0;
for(int i=1;s[i];i++)
{
int k=s[i]-'a'+1;
if(!t[x].nex[k])return 0;
x=t[x].nex[k];
}
return prefix?t[x].pfx:t[x].wd;
}
void update(char *pre,char *now)
{
int x=get_idx(pre);
if(!~x)
{
puts("Empty");
return;
}
int y=get_idx(now);
if(~y)
{
puts("Conflict");
return;
}
node p=t[x];
erase(pre,p.pfx,true);
int z=insert(now,p.pfx,true);
t[z].wd=p.wd;
for(int i=1;i<=26;i++)
{
t[z].nex[i]=p.nex[i];
if(p.nex[i])t[p.nex[i]].nex[0]=z;
}
}
void clear(){M.clear();t[0].clear();}
}T;
01字典树
struct Trie
{
struct node
{
int nex[2],num;
void clear() {mem(nex,0),num=0;}
}t[10000000];
Trie() {t[0].clear();}
void insert(int x,int val)
{
int y=0;
for(int i=1<<30;i;i>>=1)
{
int k=(x&i)?1:0;
if(!t[y].nex[k])
t[y].nex[k]=M.get();
y=t[y].nex[k];
t[y].num+=val;
}
}
int get_max(int x)
{
int y=0,ans=0;
for(int i=1<<30;i;i>>=1)
{
int k=(x&i)?1:0;
if(t[t[y].nex[!k]].num)
y=t[y].nex[!k],ans|=i;
else y=t[y].nex[k];
}
return ans;
}
}T;
网友评论