题目大意
题目分析
对所有字符串建立trie树，trie树上每个结点保存使出现次数递增的历史位置，查询时二分即可，不需要可持久化，因为保存了历史位置，直接删除也可以。
时间复杂度$O(n\log n)$。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Trie {
struct Tree {
int cnt;
vector<pii> t;
int child[10];
} tree[maxn*60];
int size;
void insert(string s,int t) {
int x=0;
for(auto ch:s) {
int y=ch-'a';
if(tree[x].child[y]==0)tree[x].child[y]=++size;
x=tree[x].child[y];
tree[x].cnt++;
if(tree[x].t.empty()||tree[x].t.back().first<tree[x].cnt)tree[x].t.push_back(mp(tree[x].cnt,t));
}
}
void del(string s) {
int x=0;
for(auto ch:s) {
int y=ch-'a';
x=tree[x].child[y];
tree[x].cnt--;
}
}
int query(string s,int val) {
int x=0;
for(auto ch:s) {
int y=ch-'a';
x=tree[x].child[y];
if(!x)return -1;
}
if(tree[x].t.empty()||tree[x].t.back().first<val)return -1;
int Left=0,Right=tree[x].t.size()-1;
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(tree[x].t[mid].first<val)Left=mid+1;
else Right=mid-1;
}
return tree[x].t[Left].second;
}
} trie;
char s[65];
int n,lastans;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int opt=Get_Int();
scanf("%s",s);
int len=strlen(s);
if(opt==1)trie.insert(s,i);
else if(opt==2)trie.del(s);
else {
int a=Get_Int(),b=Get_Int(),c=Get_Int();
lastans=abs(lastans);
int val=((long long)a*lastans+b)%c+1;
lastans=trie.query(s,val);
printf("%d\n",lastans);
}
}
return 0;
}
|
