「HAOI2018」字串覆盖
这自然有后缀数组和后缀自动的写法，我写的是后缀数组
现对于(A,B)两串拼接后建立( ext{SA})
对于查询的四个参数([s,t,l,r])，在( ext{SA})上找到能够匹配([l,r])的( ext{rank})区间([l',r'])
这个([l',r'])就用( ext{SA})的( ext{height})数组上倍增即可(O(log n))找到
由于(K>n)，显然覆盖就是从左到右依次匹配每个( ext{rank})在([l',r'])中的(i)，能放就放
数据范围提示我们切分写
Part1 (r-lleq 50)
对于每种不同的(r-l)，倍增预处理
我们将依次匹配的过程描述成一个个跳跃
对于每个(i)找到后面第一个(j)满足(j>i+r-l, ext{LCP}(i,j)ge r-l+1)
具体的，将( ext{SA})的( ext{height})数组按照( ext{height}_pge r-l+1)分成一段一段
每个连续段中的两个位置( ext{LCP}ge r-l+1)
合法的(i,j)一定出现的某个连续段中
找到每一个这样一个连续段，然后双指针得到合法的(i,j)即可
[
]
这样的跳跃关系，以及跳跃过程中的答案，可以通过倍增来维护出来
对于每个询问，可以先找到区间内第一个合法的点(i_0)，然后倍增查询答案即可
找到(i_0)可以用主席树二分出( ext{rank})在([l',r'])内的第一个(i_0ge s)的位置
复杂度为(O(50nlog n+qlog n))
[
]
Part2 (r-l>50)
根据数据范围，这里我们只要能够暴力跳每一个合法的(i)即可
那么像上面一样，用主席树每次找([l',r'])内第一个(i'> i+r-l)
每次(log n)跳即可，复杂度为(O(frac{nq}{r-l}log n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
int s=0,f=0;
while(!isdigit(IO=getchar())) f|=IO=='-';
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=2e5+10,M=N*18,S=60;
int n,K,q;
char s[N];
int cnt[N],rk[N<<1],tmp[N],sa[N];
int st[19][N],Log[N];
void Build() {
rep(i,1,n) cnt[(int)s[i]]++;
rep(i,1,200) cnt[i]+=cnt[i-1];
drep(i,n,1) sa[cnt[(int)s[i]]--]=i;
rep(i,1,n) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
for(int m=rk[sa[n]],k=1;k<n && m<n;k<<=1,m=rk[sa[n]]) {
int h=0;
rep(i,n-k+1,n) tmp[++h]=i;
rep(i,1,n) if(sa[i]>k) tmp[++h]=sa[i]-k;
memset(cnt,0,(m+1)<<2);
rep(i,1,n) cnt[rk[i]]++;
partial_sum(cnt+1,cnt+m+1,cnt+1);
drep(i,n,1) sa[cnt[rk[tmp[i]]]--]=tmp[i];
rep(i,1,n) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+k]!=rk[sa[i-1]+k]);
memcpy(rk,tmp,(n+1)<<2);
}
rep(i,2,n) Log[i]=Log[i>>1]+1;
int h=0;
rep(i,1,n) {
int j=sa[rk[i]-1];
if(h) h--;
while(s[i+h]==s[j+h]) h++;
st[0][rk[i]-1]=h;
}
rep(i,1,Log[n]) {
int len=1<<(i-1);
rep(j,1,n-len+1) st[i][j]=min(st[i-1][j],st[i-1][j+len]);
}
}
int ls[M],rs[M],c[M],rt[N],tcnt;
void Upd(int &p,int pre,int l,int r,int x){
c[p=++tcnt]=c[pre]+1,ls[p]=ls[pre],rs[p]=rs[pre];
if(l==r) return;
int mid=(l+r)>>1;
x<=mid?Upd(ls[p],ls[pre],l,mid,x):Upd(rs[p],rs[pre],mid+1,r,x);
}
int Que(int p1,int p2,int l,int r,int x){
if(c[p1]==c[p2] || r<x) return n+1;
if(l==r) return l;
int mid=(l+r)>>1,t=Que(ls[p1],ls[p2],l,mid,x);
return t<=n?t:Que(rs[p1],rs[p2],mid+1,r,x);
}
vector <int> G[S];
int A[N],B[N],L[N],R[N],X[N];
ll ans[N];
ll H[20][N]; int F[20][N];
int D[N],C;
int main(){
n=rd(),K=rd();
scanf("%s",s+1),scanf("%s",s+n+1);
n*=2,Build(),n/=2;
rep(i,1,n*2) {
rt[i]=rt[i-1];
if(sa[i]<=n) Upd(rt[i],rt[i],1,n,sa[i]);
}
rep(i,1,q=rd()) {
A[i]=rd(),B[i]=rd();
int l=rd(),x=rd()-l+1,r=l=rk[l+n];
drep(j,18,0) {
if(r+(1<<j)<=n*2 && st[j][r]>=x) r+=1<<j;
if(l>(1<<j) && st[j][l-(1<<j)]>=x) l-=1<<j;
}
L[i]=l,R[i]=r,X[i]=x;
if(n<=5000 && q<=5000) {
int p=A[i],e=B[i]-x+1;
while(p<=e) {
while(p<=e && (rk[p]<l || rk[p]>r)) p++;
if(p>e) break;
ans[i]+=K-p,p+=x;
}
} else if(X[i]>=S) {
int p=A[i],e=B[i]-x+1;
while(p<=e) {
int c=0;
while(++c<5 && p<=e && (rk[p]<l || rk[p]>r)) p++;
if(p>e) break;
if(rk[p]<l || rk[p]>r) p=Que(rt[l-1],rt[r],1,n,p);
if(p>e) break;
ans[i]+=K-p,p+=x;
}
} else G[X[i]].pb(i);
}
rep(x,1,S-1) if(G[x].size()) {
rep(i,1,n) F[0][i]=n+1;
rep(i,0,17) F[i][n+1]=n+1;
rep(i,1,n*2) {
int j=i;
while(j<n*2 && st[0][j]>=x) j++;
C=0;
rep(k,i,j) if(sa[k]<=n) D[++C]=sa[k];
if(C) {
sort(D+1,D+C+1);
int j=1;
rep(i,1,C) {
while(j<=C && D[j]-D[i]<x) j++;
if(j<=C) F[0][D[i]]=D[j];
}
}
i=j;
}
rep(i,1,n) H[0][i]=K-i;
rep(j,1,17) rep(i,1,n) {
F[j][i]=F[j-1][F[j-1][i]];
H[j][i]=H[j-1][i]+H[j-1][F[j-1][i]];
}
rep(d,0,G[x].size()-1) {
int i=G[x][d],e=B[i]-x+1;
int p=Que(rt[L[i]-1],rt[R[i]],1,n,A[i]);
if(p>e) continue;
drep(j,17,0) if(F[j][p]<=e) {
ans[i]+=H[j][p];
p=F[j][p];
}
ans[i]+=H[0][p];
}
}
rep(i,1,q) printf("%lld
",ans[i]);
}