前缀查询（字典树+线段树懒惰标记）

159 阅读 0 评论 105 点赞

我是靠谱客的博主飞快星月，这篇文章主要介绍前缀查询（字典树+线段树懒惰标记），现在分享给大家，希望可以做个参考。

描述
在一个 Minecraft 村庄中，村长有这一本小写字母构成的名册（字符串的表），
每个名字旁边都记录着这位村民的声望值，而且有的村民还和别人同名。
随着时间的推移，因为没有村民死亡，这个名册变得十分大。
现在需要您来帮忙维护这个名册，支持下列 4 种操作：
1. 插入新人名 si，声望为 ai
2. 给定名字前缀 pi 的所有人的声望值变化 di
3. 查询名字为 sj 村民们的声望值的和（因为会有重名的）
4. 查询名字前缀为 pj 的声望值的和
输入描述:
第一行为两个整数 0 ≤ N ≤ 105，表示接下来有 N 个操作；
接下来 N 行，每行输入一个操作，行首为一个整数 1 ≤ oi ≤ 4，表示这一行的操作的种类，
那么这一行的操作和格式为：
1. 插入人名，这一行的格式为 1 si ai，其中 |ai| ≤ 103
2. 前缀修改声望，这一行的格式为 2 pi di，其中 |di| ≤ 103
3. 查询名字的声望和，这一行的格式为 3 sj
4. 查询前缀的声望和，这一行的格式为 4 pj
输入保证插入人名的字符串的长度和小于或等于 105，总的字符串的长度和小于或等于 106。
输出描述:
对于每一次询问操作，在一行里面输出答案。
示例1
输入
20
1 a -10
1 abcba -9
1 abcbacd 5
4 a
2 a 9
3 aadaa
3 abcbacd
4 a
3 a
2 a 10
3 a
2 a -2
2 d -8
1 ab -2
2 ab -7
1 aadaa -3
4 a
3 abcba
4 a
4 c
输出
-14
0
14
13
-1
9
11
1
11
0

思路：

看到这个，很明显的字典树，但是有一个前缀修改，这个只用字典树实现不了，但是应用了线段树的懒惰标记就可以了。

调试了好久，经过不懈努力，终于把这道题给补上了。

代码：

复制代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=110000;
struct Node
{
    LL sum,va;
    int qian,same;
    LL d;
    int ch[30];
}G[maxn];
int ans,root;
inline int idx(char x)
{
    return x-'a';
}
void pushdown(int u)
{
    if(u&&G[u].d)
    {
        for(int i=0;i<26;i++)
        {
            if(G[u].ch[i])continue;
            G[G[u].ch[i]].d+=G[u].d;
            G[G[u].ch[i]].sum+=G[G[u].ch[i]].qian*G[u].d;
            G[G[u].ch[i]].va+=G[G[u].ch[i]].same*G[u].d;
        }
        G[u].d=0;
    }
}
void inset(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])
        {
            G[u].ch[v]=++ans;
        }
        G[u].qian++;
        G[u].sum+=val;
        u=G[u].ch[v];
        pushdown(u);
    }
    G[u].qian++;
    G[u].sum+=val;
    G[u].same++;
    G[u].va+=val;
}

void update(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        u=G[u].ch[v];
    }
    int qian=G[u].qian;
    u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        G[u].sum+=qian*val;
        u=G[u].ch[v];
        pushdown(u);
    }

G[u].sum+=qian*val;
    G[u].va+=G[u].same*val;
    G[u].d+=val;
}
LL select1(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].va;
}
LL select2(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].sum;
}
char b[maxn];
int t,k,w;
int main()
{
    ans=1;
    root=1;
    memset(G,0,sizeof(G));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%s %d",b,&w);
            inset(b,w);
        }
        else if(k==2)
        {
            scanf("%s %d",b,&w);
            update(b,w);
        }
        else if(k==3)
        {
            scanf("%s",b);
            printf("%lldn",select1(b));
        }
        else if(k==4)
        {
            scanf("%s",b);
            printf("%lldn",select2(b));
        }
    }
    return 0;
}

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=110000;
struct Node
{
    LL sum,va;
    int qian,same;
    LL d;
    int ch[30];
}G[maxn];
int ans,root;
inline int idx(char x)
{
    return x-'a';
}
void pushdown(int u)
{
    if(u&&G[u].d)
    {
        for(int i=0;i<26;i++)
        {
            if(G[u].ch[i])continue;
            G[G[u].ch[i]].d+=G[u].d;
            G[G[u].ch[i]].sum+=G[G[u].ch[i]].qian*G[u].d;
            G[G[u].ch[i]].va+=G[G[u].ch[i]].same*G[u].d;
        }
        G[u].d=0;
    }
}
void inset(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])
        {
            G[u].ch[v]=++ans;
        }
        G[u].qian++;
        G[u].sum+=val;
        u=G[u].ch[v];
        pushdown(u);
    }
    G[u].qian++;
    G[u].sum+=val;
    G[u].same++;
    G[u].va+=val;
}

void update(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        u=G[u].ch[v];
    }
    int qian=G[u].qian;
    u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        G[u].sum+=qian*val;
        u=G[u].ch[v];
        pushdown(u);
    }

    G[u].sum+=qian*val;
    G[u].va+=G[u].same*val;
    G[u].d+=val;
}
LL select1(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].va;
}
LL select2(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].sum;
}
char b[maxn];
int t,k,w;
int main()
{
    ans=1;
    root=1;
    memset(G,0,sizeof(G));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%s %d",b,&w);
            inset(b,w);
        }
        else if(k==2)
        {
            scanf("%s %d",b,&w);
            update(b,w);
        }
        else if(k==3)
        {
            scanf("%s",b);
            printf("%lldn",select1(b));
        }
        else if(k==4)
        {
            scanf("%s",b);
            printf("%lldn",select2(b));
        }
    }
    return 0;
}