5-1串 - nszkay

字典树#

字典树(普通版本)#

以26个小写的英文字母为例子

1
#include <bits/stdc++.h>
2
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
3
#define fix(x) fixed<<setprecision(x)
4
#define int long long
5
using namespace std;
6
template<class T>
7
using ve=vector<T>;
8
using ll = long long;
9
using ld = long double;
10
using pii = pair<int, int>;
11
const int N = 1e6 + 10;
12
const int mod = 1e9 + 7;
13

14
struct TIE
15
{
16
    ve<ve<int>>ti;
17
    ve<int>sum;
18
    int cnt;
19
    TIE(int n)
20
    {
21
        cnt=1;//
22
        ti=ve<vector<int>>(n+1,ve<int>(30,-1));
23
        sum=ve<int>(n+1,0);
24
    }
25

26
    int get_sum(char x)
27
    {
28
        if(x>='a'&&x<='z') return x-'a';//0-26
29
        if(x>='A'&&x<='Z') return x-'A'+26;
30
        return x-'0'+52;
31
    }
32

33
    void insert(const string& s)
34
    {//
35
        int ls=0;
36
        for(auto x:s)
37
        {
38
            if(ti[ls][get_sum(x)]==-1) ti[ls][get_sum(x)]=cnt++;
39
            ls=ti[ls][get_sum(x)];
40
            sum[ls]++;
41
        }
42
    }
43

44
    int query_sum(const string& s)
45
    {
46
        int ls=0;
47
        for(auto x:s)
48
        {
49
            if(ti[ls][get_sum(x)]==-1) return 0;
50
            ls=ti[ls][get_sum(x)];
51
        }
52
        return sum[ls];
53
    }
54
};
55

56
void solve()
57
{
58
    int n,q;cin>>n>>q;
59
    TIE tr(3e6);
60
    for(int i=1;i<=n;i++)
61
    {
62
        string s;cin>>s;
63
        tr.insert(s);
64
    }
65
    while(q--)
66
    {
67
        string s;cin>>s;
68
        cout<<tr.query_sum(s)<<'\n';
69
    }
70
}
71
signed main()
72
{
73
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
74
    int _=1; cin>>_;
75
    while(_--) solve();
76
    return 0;
77
}

可持久化字典树#

1
#include <bits/stdc++.h>
2
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
3
#define fix(x) fixed<<setprecision(x)
4
#define int long long
5
using namespace std;
6
template<class T>
7
using ve=vector<T>;
8
using pii = pair<int, int>;
9
const int N = 1e6 + 10;
10
const int mod = 1e9 + 7;
11

12
int n,m;
13
int ti[N*25][2];
14
int sz[N*25],rt[N*25],siz[N*25];
15
int cnt=0,idx=0;
16

17
void insert(int x)
18
{//0--24
19
    rt[++idx]=++cnt;//开新的版本
20
    int ls=rt[idx-1];//上一个版本
21
    int rs=rt[idx];//当前版本
22
    for(int i=23;i>=0;i--)
23
    {
24
        int j=(x>>i)&1;         //
25
        ti[rs][j^1]=ti[ls][j^1];//继承
26

27
        ti[rs][j]=++cnt;        //开新的节点
28
        ls=ti[ls][j];
29
        rs=ti[rs][j];
30
        siz[rs]=siz[ls]+1;
31
    }
32
}
33

34
int query(int l,int r,int p)
35
{
36
    int ls=rt[l-1];
37
    int rs=rt[r];
38

39
    int sum=0;
40
    for(int i=23;i>=0;i--)
41
    {
42
        int j=p>>i&1;
43
        if(siz[ti[rs][j^1]]>siz[ti[ls][j^1]])
44
        {//可以
45
            ls=ti[ls][j^1];
46
            rs=ti[rs][j^1];
47
            sum+=(1<<i);
48
        }
49
        else
50
        {
51
            ls=ti[ls][j];
52
            rs=ti[rs][j];
53
        }
54
    }
55
    return sum;
56
}
57

58
void solve()
59
{
60
    cin>>n>>m;
61
    int ans=0;
62
    insert(ans);
63
    for(int i=1;i<=n;i++)
64
    {
65
        int x;cin>>x;
66
        ans^=x;
67
        insert(ans);
68
    }
69
    while(m--)
70
    {
71
        char p;cin>>p;
72
        if(p=='A')
73
        {
74
            int x;cin>>x;
75
            ans^=x;
76
            insert(ans);
77
        }
78
        else
79
        {
80
            int l,r,x;cin>>l>>r>>x;
81
            cout<<query(l,r,ans^x)<<'\n';
82
        }
83
    }
84
}
85

86
signed main()
87
{
88
    IOS;
89
    int _ = 1; //cin >> _;
90
    while (_--) solve();
91
    return 0;
92
}