题意
给定一个长度为 $n$ 的字符串 $s$, $m$ 对 $(l_i,r_i)$, 回答 $q$ 个询问. 每个询问会给定一个长度为 $k$ 的字符串 $w$ 以及一对 $L,R$, 求所有满足 $i\in [L,R]$ 的 $w[l_i:r_i]$ 在 $s$ 中的出现次数之和.
$n,m,k,q\le 1\times 10^5$, $\sum |w|\le 1\times 10^5$.
题解
这sb题直接SAM暴力tm有90分…然而考场上把 $k$ 和 $q$ 读反了挂成10分…
那个 $\sum |w|$ 显然就是 $kq$, 于是 $kq\le1\times 10^5$. 我们一点都不自然地想到可以根号分类.
当 $k\le \sqrt m$ 的时候, 显然 $k^2q=O(m)k=O(m\sqrt m)$. 那么我们直接枚举 $w$ 的所有子串, 在 $s$ 的SAM上倍增计算答案, 二分计算当前查询区间中有多少个当前子串就可以统计当前子串对答案的贡献了. 时间复杂度是 $O(k^2q\log n)=O(m\sqrt m\log n)$.
当 $k>\sqrt m$ 的时候, 显然 $kq=O(m)\Rightarrow q=O(\sqrt m)$. 于是我们将所有 $(l_i,r_i)$ 分布到 $r_i$ 上, 然后边在SAM上跑边计算右端点为当前位置的子串对答案的贡献. 一次的复杂度是 $O(k+m\log n)$. 总复杂度显然是 $O(m\sqrt m \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
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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
#include <bits/stdc++.h>
namespace rvalue{
const int MAXN=2e5+10;
typedef long long intEx;
int n;
int q;
int k;
int m;
int lg;
int cnt=1;
int last=1;
int root=1;
int s[MAXN];
int prt[MAXN];
int len[MAXN];
int size[MAXN];
char buf[MAXN];
int pprt[20][MAXN];
std::map<char,int> chd[MAXN];
void Extend(char);
namespace BF1{
const int SQRN=350;
std::vector<int> qpos[SQRN][SQRN];
int main(){
#ifdef IRECT
puts("BF1");
#endif
for(int i=0;i<m;i++){
int l,r;
scanf("%d%d",&l,&r);
qpos[l][r].push_back(i);
}
while(q--){
int a,b;
scanf("%s%d%d",buf,&a,&b);
int cur=root,curlen=0;
intEx ans=0;
for(int i=0;i<k;i++){
while(cur!=root&&!chd[cur].count(buf[i])){
cur=prt[cur];
curlen=std::min(curlen,len[cur]);
}
if(chd[cur].count(buf[i])){
cur=chd[cur][buf[i]];
++curlen;
int pos=cur;
for(int plen=curlen;plen>=1;plen--){
while(len[prt[pos]]>=plen)
pos=prt[pos];
auto& q=qpos[i-plen+1][i];
auto low=std::lower_bound(q.begin(),q.end(),a);
auto up=std::upper_bound(q.begin(),q.end(),b);
int cnt=up-low;
// printf("%d len=%d cnt=%d\n",i,plen,cnt);
ans+=1ll*cnt*size[pos];
}
}
}
printf("%lld\n",ans);
}
return 0;
}
}
namespace BF2{
std::vector<std::pair<int,int>> qlen[MAXN];
int main(){
#ifdef IRECT
puts("BF2");
#endif
for(int i=0;i<m;i++){
int l,r;
scanf("%d%d",&l,&r);
qlen[r].emplace_back(r-l+1,i);
}
while(q--){
int a,b;
scanf("%s%d%d",buf,&a,&b);
int cur=root,curlen=0;
intEx ans=0;
for(int i=0;i<k;i++){
while(cur!=root&&!chd[cur].count(buf[i])){
cur=prt[cur];
curlen=std::min(curlen,len[cur]);
}
if(chd[cur].count(buf[i])){
cur=chd[cur][buf[i]];
++curlen;
for(auto q:qlen[i]){
if(q.second<a||q.second>b)
continue;
if(curlen<q.first)
continue;
int pos=cur;
for(int j=lg;j>=0;j--)
if(len[pprt[j][pos]]>=q.first)
pos=pprt[j][pos];
ans+=size[pos];
}
}
}
printf("%lld\n",ans);
}
return 0;
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&q,&k);
scanf("%s",buf);
for(int i=0;i<n;i++)
Extend(buf[i]);
for(int i=1;i<=cnt;i++)
s[i]=i;
std::sort(s+1,s+cnt+1,[](int a,int b){return len[a]>len[b];});
for(int i=1;i<=cnt;i++){
size[prt[s[i]]]+=size[s[i]];
pprt[0][i]=prt[i];
}
for(int j=1;(1<<j)<=cnt;j++){
lg=j;
for(int i=1;i<=cnt;i++)
pprt[j][i]=pprt[j-1][pprt[j-1][i]];
}
if(1ll*k*k<=m)
BF1::main();
else
BF2::main();
return 0;
}
void Extend(char x){
int p=last;
int np=++cnt;
size[last=np]=1;
len[np]=len[p]+1;
while(p&&!chd[p].count(x))
chd[p][x]=np,p=prt[p];
if(!p)
prt[np]=root;
else{
int q=chd[p][x];
if(len[q]==len[p]+1)
prt[np]=q;
else{
int nq=++cnt;
len[nq]=len[p]+1;
chd[nq]=chd[q];
prt[nq]=prt[q];
prt[q]=nq;
prt[np]=nq;
while(p&&chd[p][x]==q)
chd[p][x]=nq,p=prt[p];
}
}
}
}
int main(){
#if 0
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
#endif
rvalue::main();
return 0;
}
|
