【Trie】补退选（洛谷P5335）

题目描述

X 是一名老师，每年他都要教授许多学生基础的C++ 知识。每个学生在每学
期的开学前都需要选课，每次选课一共分为三个阶段：预选，正选，补退选；其
中「补退选」阶段最忙碌。
在补退选阶段，学生即可以选课，也可以退课。对于X 老师来说，在补退选阶
段可能发生以下两种事件：
• 一个姓名为S 的学生选了他的课（姓名S 将出现在已选课学生名单中）；
• 一个姓名为S 的学生退了他的课（姓名S 将从已选课学生名单中移除）。
同时，X 老师对于有哪些学生选了他的课非常关心，所以他会不定时的查询已
选课学生名单，每次查询为：
• 最早在哪个事件之后，姓名以S 为前缀的学生数量超过了v。
X 老师看你骨骼清奇，所以想用这个问题考考你，你当然不会畏惧，所以勇敢
的接下了这个任务。
注意1：学生的姓名可能相同，如果有p 个姓名相同的学生都选了X 老师的课，
则他们的姓名将出现在X 老师的名单上p 次。
注意2：只有已经选了课的学生才会退课，如果姓名为S 的学生退课，则在他
退课之前X 老师的名单上一定有姓名S。
注意3：选课，退课和查询都被定义为「事件」；「事件」的编号从1 开始。

输入

第一行包含一个正整数n，表示一共发生了n 个事件。
接下来n 行，每行描述一个事件；每行第一个正整数k 表示事件类型：
• 如果k = 1，表示选课事件，接下来一个字符串S，表示一个姓名为S 的
学生选了X 老师的课；
• 如果k = 2，表示退课事件，接下来一个字符串S，表示一个姓名为S 的
学生退了X 老师的课；
• 如果k = 3，表示查询事件，接下来一个字符串S 以及三个非负整数a, b, c，
表示X 老师想知道最早在第几个事件之后，姓名以S 为前缀的学生数量
超过了(a×|ans|+b) mod c，|ans| 表示上次查询事件的答案的绝对值，如
果当前是第一次查询，则|ans| = 0；如果任何时刻都没有超过该值，则答
案为−1。
注意：输入中的所有字符串均只包含前10 个小写字母。

输出

对于每个查询事件，输出一行表示该查询答案。

数据范围限制

对于10% 的数据，1 ≤ n ≤ 100。
对于20% 的数据，1 ≤ n ≤ 4000。
对于50% 的数据，1 ≤ n ≤ 30000。
对于100% 的数据，1 ≤ n ≤ 100000，1 ≤ |S| ≤ 60。

Solution：

看到前缀查询就很容易想到Trie树，本题难点在于如何实现查询最早出现位置，可持久化空间消耗太大（而且咱也不会打），离线查询也不现实，所以考场上打完trie就蒙圈了。

正解是利用vector记录trie树上每个端点第一次到达某个数值时操作的次数，查询的时候只要查到最后一个字母时对应数值第一次达到的操作次数，直接输出即可，如果不存在输出-1。强 thm 强

代码有点菜，最久的点跑了800ms。

Code：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int N,tot;
 4 int Tree[555555][10],son[555555][10];
 5 int Action[100500],Ans;
 6 char Str[66];
 7 vector<int> Mark[555555][10];
 8 void insert(int Action){
 9     int Len=strlen(Str);
10     int p=1;
11     for(int i=0;i<Len;i++){
12         int Num=Str[i]-'a';
13         Tree[p][Num]++;
14         if(Mark[p][Num].size()<Tree[p][Num]) Mark[p][Num].push_back(Action);
15         if(i==Len-1) continue;
16         if(!son[p][Num]) son[p][Num]=++tot;
17         p=son[p][Num];
18     }
19 }
20 void Delete(){
21     int Len=strlen(Str);
22     int p=1;
23     for(int i=0;i<Len;i++){
24         int Num=Str[i]-'a';
25         Tree[p][Num]--;
26         if(i==Len-1) continue;
27         p=son[p][Num];
28     }
29 }
30 void Search(int goal){
31     int Len=strlen(Str);
32     int p=1;
33     for(int i=0;i<Len;i++){
34         int Num=Str[i]-'a';
35         if(i==Len-1) continue;
36         p=son[p][Num];
37     }
38     int Num2=Str[Len-1]-'a';
39     if(Mark[p][Num2].size()>goal)
40         Ans=Mark[p][Num2][goal];
41     else Ans=-1;
42 }
43 int main()
44 {
45 //    freopen("selection.in","r",stdin);
46 //    freopen("selection.out","w",stdout);
47     int m=0;
48     tot=1;
49     scanf("%d",&N);
50     for(int __=1;__<=N;__++){
51         int Key;
52         scanf("%d",&Key);
53         if(Key==1){
54             scanf("%s",Str);
55             insert(__);
56         }
57         if(Key==2){
58             scanf("%s",Str);
59             Delete();
60         }
61         if(Key==3) {
62             scanf("%s",Str);
63             long long a,b,c;
64             cin>>a>>b>>c;
65             Search((a*Ans+b)%c);
66             cout<<Ans<<endl;
67             if(Ans==-1) Ans=1;
68         }
69     }
70     return 0;
71 }