01-trie 学习笔记

Trie

学习资料

• 字典树trie - OI Wiki
• 可持久化字典树 - OI Wiki

例题-P2580 于是他错误的点名开始了

直接建立trie，记录名单的结尾，第一次点过后标记。

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int N=5e5+10;

int n,nex[N][40],cnt=1;
char s[100];
bool in[N],done[N];

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d",&n);
    int u,c;
    for(int i=1;i<=n;i++)
    {
        scanf(" %s",s);
        u=1;
        for(int j=0;s[j];j++)
        {
            c=s[j]-'a';
            if(!nex[u][c]) nex[u][c]=++cnt;
            u=nex[u][c];
        }
        in[u]=true;
    }
    scanf("%d",&n);
    while(n--)
    {
        scanf(" %s",s);
        u=1;
        for(int j=0;s[j] && u;j++) u=nex[u][s[j]-'a'];
        if(done[u]) puts("REPEAT");
        else if(in[u]) {done[u]=true; puts("OK");}
        else puts("WRONG");
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

01-trie

这东西可以维护异或极值。

AcWing143. 最大异或对

洛谷找不到这题，只有接下来要讲的进阶版。

题目非常简洁。

在给定的 N 个整数 A_1，A_2……A_N 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

以下以李煜东蓝书中解释为基础。

将每一个数字转化成 32 位二进制数插入trie树。对于每一个数字 A_i ，插入后在trie树上尽量遍历与 A_i 当前位相反的指针。

以上策略根据 xor 运算“相同得 0 ，不同得 1”的性质得出。

至于为什么在查询前插入，是因为第一个数不会对之前插入的数进行统计，此时异或等于 0 。

打卡代码

P4551 最长异或路径

先dfs出每个节点从根到自己的异或路径做树上差分即可，trie的部分和上题没有什么差别。如果这题需要代码请回复在评论区或者私信。

可持久化字典树

P4735 最大异或和

在序列末尾添加一个数，这让我们想起主席树。

2操作刨区间也是主席树有的操作。

没错，这题是可持久化trie。

思路是OI Wiki的，代码则更加简洁，推荐一起食用。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int N=6e5+10;//双倍空间
int a[N],sum[N];
namespace trie
{
    int cnt,rt[N],tr[N << 5][2],val[N << 5];
    inline void ins(int o,int lst,int v)
    {
        for(int i=25,bit;~i;i--)
        {
            val[o]=val[lst]+1;
            bit=(v>>i)&1;
            if(!tr[o][bit]) tr[o][bit]=++cnt;
            tr[o][bit^1]=tr[lst][bit^1];//复制
            o=tr[o][bit]; lst=tr[lst][bit];
        }
        val[o]=val[lst]+1;
    }
    inline int query(int l,int r,int v)
    {
        int res=0;
        for(int i=25,bit;~i;i--)
        {
            bit=(v>>i)&1;
        //这里判断的写法是个好东西，即使你传参时lr写反了也没事
            if(val[tr[r][bit^1]]-val[tr[l][bit^1]]) {res+=(1<<i); l=tr[l][bit^1]; r=tr[r][bit^1];}
            else {l=tr[l][bit]; r=tr[r][bit];}
        }
        return res;
    }
}

using namespace trie;//坏习惯

int main()
{
//  freopen("work.in","r",stdscanfin); freopen("work.out","w",stdout);
    int n,m,l,r,x;
    char op;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]); sum[i]=sum[i-1]^a[i];}//前缀异或和
    for(int i=1;i<=n;i++) {rt[i]=++cnt; ins(rt[i],rt[i-1],sum[i]);}//复制修改路径版本
    while(m--)
    {
        scanf(" %c",&op);
        if(op == 'A')
        {
            scanf("%d",&a[++n]);
            sum[n]=sum[n-1]^a[n];
            rt[n]=++cnt; ins(rt[n],rt[n-1],sum[n]);
        }
        else
        {
            scanf("%d%d%d",&l,&r,&x);
            l--; r--;
            if(l == r && !l) printf("%d\n",sum[n]^x);
            else printf("%d\n",query(rt[max(l-1,0)],rt[r],x^sum[n]));
        }
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

闲话

某天xgf突然发现01-trie可以实现平衡树，而且常数还贼小。

01-trie有左子树上的任何数小于右子树上的任何数的性质。

我太菜了不会实现，大家有兴趣实现了的话记得踢我让我开开眼界。

The End

关于其他trie的用法在OI Wiki中有介绍，由于作者还没学故没有出现在笔记中。接下来的话看心情更新。