前缀查询(字典树+延迟更新)

描述

传送门:Wannafly挑战赛14 - Problem B

在一个 Minecraft 村庄中,村长有这一本小写字母构成的名册(字符串的表),
每个名字旁边都记录着这位村民的声望值,而且有的村民还和别人同名。
随着时间的推移,因为没有村民死亡,这个名册变得十分大。
现在需要您来帮忙维护这个名册,支持下列 4 种操作:

  1. 插入新人名 $s_i$,声望为 $a_i$
  2. 给定名字前缀 $p_i$ 的所有人的声望值变化 $d_i$
  3. 查询名字为 $s_j$ 村民们的声望值的和(因为会有重名的)
  4. 查询名字前缀为 $p_j$ 的声望值的和

输入描述

第一行为两个整数 $0 ≤ N ≤ 10^5$,表示接下来有 $N$ 个操作;
接下来 $N$ 行,每行输入一个操作,行首为一个整数 $1 ≤ o_i ≤ 4$,表示这一行的操作的种类,
那么这一行的操作和格式为:

  1. 插入人名,这一行的格式为 $1 s_i a_i$,其中 $|a_i| ≤ 10^3$
  2. 前缀修改声望,这一行的格式为 $2 p_i d_i$,其中 $|d_i| ≤ 10^3$
  3. 查询名字的声望和,这一行的格式为 $3 s_j$
  4. 查询前缀的声望和,这一行的格式为 $4 p_j$
    输入保证插入人名的字符串的长度和小于或等于 $10^5$,总的字符串的长度和小于或等于 $10^6$。

输出描述

对于每一次询问操作,在一行里面输出答案。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

样例输出

1
2
3
4
5
6
7
8
9
10
-14
0
14
13
-1
9
11
1
11
0

思路

  • 看一眼就知道要用字典树来维护。
  • 难点在于如何处理要维护的信息。
  • 我们需要维护前缀和,前缀个数,当前单词的权值和,当前单词的个数,以及懒惰标记五个东西。
  • 主要难点在于更新前缀的懒惰更新,以及pushup的操作。(具体实现时用一个栈,或者递归)

代码

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
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

struct Node
{
Node* ch[26];
ll sum, val, add;
int sz, cnt;
Node() { sum = val = sz = cnt = add = 0, memset(ch, 0, sizeof(ch)); }
void pushdown()
{
if (add == 0) return;
for (int i = 0; i < 26; i++)
{
if (ch[i] == nullptr) continue;
ch[i]->sum += add * ch[i]->sz;
ch[i]->val += add * ch[i]->cnt;
ch[i]->add += add;
}
add = 0;
}
};
struct Trie
{
Node* rt;
Trie() { rt = new Node; }
~Trie() { destory(rt); }
void destory(Node* o)
{
if (o == nullptr) return;
for (int i = 0; i < 26; i++) destory(o->ch[i]);
delete o;
}
void insert(const char* s, int v)
{
Node* u = rt;
for (int i = 0; s[i]; i++)
{
u->pushdown();
u->sum += v, u->sz++;
int c = s[i] - 'a';
if (u->ch[c] == nullptr) u->ch[c] = new Node;
u = u->ch[c];
}
u->pushdown();
u->sum += v, u->sz++;
u->val += v, u->cnt++;
}
void update(const char* s, int v)
{
Node* u = rt;
stack<Node*> stk;
for (int i = 0; s[i]; i++)
{
int c = s[i] - 'a';
if (u->ch[c] == nullptr) u->ch[c] = new Node;
stk.push(u);
u = u->ch[c];
}
u->sum += u->sz * v;
u->val += u->cnt * v;
u->add += v;
ll tmp = u->sz * v;
while (!stk.empty()) stk.top()->sum += tmp, stk.pop();
}
ll query(const char* s, bool op = false)
{
Node* u = rt;
for (int i = 0; s[i]; i++)
{
u->pushdown();
int c = s[i] - 'a';
if (u->ch[c] == nullptr) return 0;
u = u->ch[c];
}
u->pushdown();
return op ? u->sum : u->val;
}
};
const int N = 1 << 17;
char buf[N];

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
Trie t;
int n;
scanf("%d", &n);
while (n--)
{
static int op, x;
scanf("%d", &op);
if (op == 1) scanf("%s%d", buf, &x), t.insert(buf, x);
if (op == 2) scanf("%s%d", buf, &x), t.update(buf, x);
if (op == 3) scanf("%s", buf), printf("%lld\n", t.query(buf));
if (op == 4) scanf("%s", buf), printf("%lld\n", t.query(buf, true));
}
return 0;
}
捐助作者
0%