Eternity

Until The End

字典树

发表于 更新于 分类于 ，
本文字数： 12k 阅读时长 ≈ 11 分钟

“当树的轮廓开始浮现，应有的字样也随之而来。”

学习笔记补完计划

Trie

中文名字典树，也称前缀树，是AC 自动机的组成部分之二。（另一个是 KMP ），用于匹配字符串前缀。大概样子如下图所示：

对于很多个模式串 $s_i$ ，如果其前缀有相同的部分，则我们就不需要重新创立一些新的节点，而是从两个不同字符串开始不同的地方延申出另一个节点即可。

实现

插入

1
2
3
4
5
6
7
8
9
inline void insert(char *s)
{
    int u=0,len=strlen(s+1);	//根节点
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][s[i]]) Tre[u][s[i]]=++Cnt;	//建立新节点
        u=Tre[u][s[i]];			//往后跳
    }
}

查询

该代码主要查询到是当前字符串是否在模式串中做过前缀子串。

1
2
3
4
5
6
7
8
9
10
inline bool query(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][s[i]]) return 0;		//不存在
        u=Tre[u][s[i]];
	}
    return 1;		//存在
}

例题

弱化版

如上，多了一个 REPEAT 操作。将每一个名字的最后一个字母的位置记为 $End[u]=id$ ，然后每次到达时判断 $vis[End[u]]$ 是否到达过，而判断是 REPEAT 还是 RIGHT 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
int Root,Tot;
bool End[500001*27];
int Son[500001][27];
char str[51];
inline void underInsert()
{
    int U=Root;
    for(int i=1;str[i];++i)
    {
        if(!Son[U][str[i]-'a'])
        {
            Son[U][str[i]-'a']=++Tot;
        }
        U=Son[U][str[i]-'a'];
    }
}
inline void underCheck()
{
    int U=Root;
    for(int i=1;str[i];++i)
    {
        if(!Son[U][str[i]-'a'])
        {
            printf("WRONG\n");
            return ;
        }
        if(!str[i+1])
        {
            if(End[Son[U][str[i]-'a']])
            {
                printf("REPEAT\n");
            }
            else
            {
                End[Son[U][str[i]-'a']]=1;
                printf("OK\n");
            }
            return ;
        }
        U=Son[U][str[i]-'a'];
    }
    return ;
}
int main()
{
    int N,M;
    Root=Tot=1;
    scanf("%d",&N);
    for(int i=1;i<=N;++i)
    {
        cin>>str+1;
        underInsert();
    }
    scanf("%d",&M);
    for(int i=1;i<=M;++i)
    {
        cin>>str+1;
        underCheck();
    }
    system("pause");
    return 0;
}

加强版

多了大写字母和数字。所以在建树时需要多建一点（小心爆栈）。当然，如果不太清楚会有多少种情况也是可以用 map 的。（这道题 map 会炸，亲测），因为多组数据，所以要预处理，这道题甚至卡了 memset ，所以就需要手动赋值。本题不卡常。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXS=3e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,N,Q,Cnt,End[MAXS];
int Tre[MAXS][71],Total;
std::map<char,int>Idx;
char Str[MAXS];
inline void insert(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][Idx[s[i]]]) Tre[u][Idx[s[i]]]=++Cnt;
        u=Tre[u][Idx[s[i]]];
        ++End[u];
    }
}
inline int query(char *s)
{
    int u=0,len=strlen(s+1);
    for(int i=1;i<=len;++i)
    {
        if(!Tre[u][Idx[s[i]]]) return 0;
        u=Tre[u][Idx[s[i]]];
    }
    return End[u];
}

int main()
{
    // freopen("trie.in","r",stdin);
    // freopen("trie.out","w",stdout);
    read(Test);
    for(char c='A';c<='Z';++c) Idx[c]=++Total;
    for(char c='a';c<='z';++c) Idx[c]=++Total;
    for(char c='0';c<='9';++c) Idx[c]=++Total; 
    while(Test--)
    {
        read(N,Q);Cnt=0;
        for(int i=1;i<=N;++i) scanf("%s",Str+1),insert(Str);
        for(int i=1;i<=Q;++i) scanf("%s",Str+1),printf("%d\n",query(Str));
        for(int i=0;i<=Cnt;++i)
        {
            End[i]=0;
            for(int j=0;j<=70;++j)
                Tre[i][j]=0;
        }
    }
    return 0;
}
/*
3
3 3
fusufusu
fusu
anguei
fusu
anguei
kkksc
5 2
fusu
Fusu
AFakeFusu
afakefusu
fusuisnotfake
Fusu
fusu
1 1
998244353
9
*/

CF1312G

按题意建 trie 树，并进行 dp 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Tre[MAXN<<1][27],N,K;
char str[20];
int Delta,query[MAXN],dp[MAXN];
bool End[MAXN];
struct Sk
{
    int val,id;
    Sk(int v=0,int i=0):val(v),id(i){}
};
stack<Sk>S;
void Search(int u)
{
    while(S.empty()||dp[u]-Delta<S.top().val) S.push(Sk(dp[u]-Delta,u));
    Delta+=End[u];
    for(int i=0;i<=25;++i)
    {
        if(!Tre[u][i]) continue;
        dp[Tre[u][i]]=dp[u]+1;
        if(!S.empty()&&End[Tre[u][i]])
            dp[Tre[u][i]]=min(dp[Tre[u][i]],S.top().val+Delta+1);
        Search(Tre[u][i]); 
    }
    if(!S.empty()&&S.top().id==u) S.pop();
}
int main()
{
    // freopen("trie.in","r",stdin);
    // freopen("trie.out","w",stdout);
    read(N);
    memset(dp,0x3f,sizeof(dp));
    for(int i=1,x;i<=N;++i)
    {
        read(x);
        scanf("%s",str+1);
        Tre[x][str[1]-'a']=i;
    }
    read(K);
    for(int i=1;i<=K;++i) read(query[i]),End[query[i]]=1;
    dp[0]=0;
    Search(0);
    for(int i=1;i<=K;++i) printf("%d ",dp[query[i]]);
    return 0;
}
/*
10
0 i
1 q
2 g
0 k
1 e
5 r
4 m
5 h
3 p
3 e
5
8 9 1 10 6
*/

01-Trie

顾名思义，每一个结点至多有 $2$ 个儿子，一个表示 $1$ ，一个表示 $0$ 。可以用来处理很多与位运算有关的题。

实际上 $\text{01-Trie}$ 能够作为一种平衡树，维护平衡树能够做的很多操作。

最长异或路径

首先应该知道一些关于位运算的公式：

1
x^0=x,x^x=0

那么，异或运算满足差分性，对于 $d(l,r)$ ，我们可以化成 $d(1,l)\ xor\ d(1,r)$ 来进行预处理以达到 $\mathcal O(1)$ 的复杂度来查询。

1
1^1=0,1^0=1,0^1=1,0^0=0

根据异或的性质，我们需要在所有结果中找到位数不相同最多且尽量在高位的两个，但是逐二比较的时间复杂度过高，必须更换形式：

01-trie 树可以解决这个问题。

我们将每一个异或值变成一个仅含 $01$ 的字符串并添加到 trie 树里（从高位往低位以满足答案偏大）。对于这些答案，如果有相异的值，则统计入答案，否则继续查找，这样把每一个值都查找一遍其对应值，最后取最大即可。

时间复杂度是线性的，但带有常数，约为 $\mathcal O(30n)$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=2e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N;
struct Tree
{
    int next,to,val;
    Tree(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=Tree(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Tree(Head[v],u,w);Head[v]=Total;
}
int Xor[MAXN];
void dpTree(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        Xor[v]=Xor[x]^Edge[e].val;
        dpTree(v,x);
    }
}
int Tre[MAXN][2],Idx,ans;
inline void Insert(int x)
{
    int u=0;
    for(int i=(1<<30);i;i>>=1)
    {
        bool v=x&i;
        if(!Tre[u][v]) Tre[u][v]=++Idx;
        u=Tre[u][v];
    }
}
inline int query(int x)
{
    int res=0,u=0;
    for(int i=(1<<30);i;i>>=1)
    {
        bool v=x&i;
        if(Tre[u][!v]) res+=i,u=Tre[u][!v];
        else u=Tre[u][v];
    }
    return res;
}
int main()
{
    // freopen("01-trie.in","r",stdin);
    // freopen("01-trie.out","w",stdout);
    read(N);
    for(int i=2,u,v,w;i<=N;++i)
    {
        read(u,v,w);
        addEdge(u,v,w);
    }
    dpTree(1,0);
    for(int i=1;i<=N;++i) Insert(Xor[i]);
    for(int i=1;i<=N;++i) ans=max(ans,query(Xor[i]));
    printf("%d",ans);
    return 0;
}
/*
4
1 2 3
2 3 4
2 4 6
*/

可持久化 Trie

其思想和主席树是有类似的，对于原有的部分直接牵引，而无需新建结点来浪费空间。

建树步骤（插入字符串 $s$ ）：

  1. 设当前树的根节点为 $rt$ ，令 $p=rt,i=0$ ；
  2. 建立新的节点 $q$ ，并执行 $rt’=q$ ；
  3. 若 $p\ne 0$ ，则有 $Trie[q][c]=Trie[p][c]$ ；
  4. 建立新的节点 $q’$ ，令 $Trie[q][s_i]=q’$ 。即除了 $s_i$ 的指针不同，$p$ 和 $q$ 保持一致；
  5. 令 $p=Trie[p][s_i],q=Trie[q][s_i],i=i+1$ ；
  6. 重复步骤 $3\sim 5$ 直到字符串遍历完成。

构建可持久化 $\text{Trie}$ 树所需的空间和时间复杂度都是字符串总长度的线性函数。

可持久化字典树

数据可能有些问题，我也不太清楚自己写对没有，而且感觉好像暴力了。

$\text{RE,TLE,MLE}$ 交替表演。

所以，题面可以给出一个思考，但代码和数据的可行度，不太高。

欢迎各种方式的 $\text{Hack}$ 。

最大异或和

对于查询，很明显有 $a[p]\ xor\ a[p+1]\ xor…\ xor\ a[N]\ xor\ x=s[p-1]\ xor\ s[N]\ xor\ x$ 的性质。

然后使用类似于 $\text{01-Trie}$ 的方法将所有的 $s$ 都插入到树中，查询其最大值，但是要满足于 $l\le p\le r$ 的条件，所以考虑可持久化。

余下的我也没学懂，贺过去的，想学的自己看题解吧。qwq

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=6e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M;
int Trie[MAXN*24][2],End[MAXN*24];
int S[MAXN],Rt[MAXN],Idx;
void Insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        End[q]=i;
        return ;
    }
    int c=S[i]>>k&1;
    if(p) Trie[q][c^1]=Trie[p][c^1];
    Trie[q][c]=++Idx;
    Insert(i,k-1,Trie[p][c],Trie[q][c]);
    End[q]=max(End[Trie[q][0]],End[Trie[q][1]]);
}
int query(int now,int val,int k,int inf)
{
    if(k<0) return S[End[now]]^val;
    int c=val>>k&1;
    if(End[Trie[now][c^1]]>=inf)
        return query(Trie[now][c^1],val,k-1,inf);
    else return query(Trie[now][c],val,k-1,inf);
}
char opt[3];
int main()
{
    // freopen("trie.in","r",stdin);
    // freopen("trie.out","w",stdout);
    read(N,M);
    End[0]=-1;Rt[0]=++Idx;
    Insert(0,23,0,Rt[0]);
    for(int i=1,x;i<=N;++i)
    {
        read(x);
        S[i]=S[i-1]^x;
        Rt[i]=++Idx;
        Insert(i,23,Rt[i-1],Rt[i]);
    }
    for(int i=1;i<=M;++i)
    {
        scanf("%s",opt+1);
        if(opt[1]=='A')
        {
            int Qx;read(Qx);
            Rt[++N]=++Idx;
            S[N]=S[N-1]^Qx;
            Insert(N,23,Rt[N-1],Rt[N]);
        }
        else
        {
            int Ql,Qr,Qx;read(Ql,Qr,Qx);
            printf("%d\n",query(Rt[Qr-1],Qx^S[N],23,Ql-1));
        }
    }
    return 0;
}
/*
5 5
2 6 4 3 6
A 1 
Q 3 5 4 
A 4
Q 5 7 0 
Q 3 6 6 
*/
相关文章