「HAOI2018」字串覆盖

这自然有后缀数组和后缀自动的写法，我写的是后缀数组

现对于$A,B$两串拼接后建立$\text{SA}$

对于查询的四个参数$[s,t,l,r]$，在$\text{SA}$上找到能够匹配$[l,r]$的$\text{rank}$区间$[l’,r’]$

这个$[l’,r’]$就用$\text{SA}$的$\text{height}$数组上倍增即可$O(\log n)$找到

由于$K>n$，显然覆盖就是从左到右依次匹配每个$\text{rank}$在$[l’,r’]$中的$i$，能放就放

数据范围提示我们切分写

Part1 $r-l\leq 50$

对于每种不同的$r-l$，倍增预处理

我们将依次匹配的过程描述成一个个跳跃

对于每个$i$找到后面第一个$j$满足$j>i+r-l,\text{LCP}(i,j)\ge r-l+1$

具体的，将$\text{SA}$的$\text{height}$数组按照$\text{height}_p\ge r-l+1$分成一段一段

每个连续段中的两个位置$\text{LCP}\ge r-l+1$

合法的$i,j$一定出现的某个连续段中

找到每一个这样一个连续段，然后双指针得到合法的$i,j$即可

这样的跳跃关系，以及跳跃过程中的答案，可以通过倍增来维护出来

对于每个询问，可以先找到区间内第一个合法的点$i_0$，然后倍增查询答案即可

找到$i_0$可以用主席树二分出$\text{rank}$在$[l’,r’]$内的第一个$i_0\ge s$的位置

复杂度为$O(50n\log n+q\log n)$

Part2 $r-l>50$

根据数据范围，这里我们只要能够暴力跳每一个合法的$i$即可

那么像上面一样，用主席树每次找$[l’,r’]$内第一个$i’> i+r-l$

每次$\log n$跳即可，复杂度为$O(\frac{nq} {r-l}\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
#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\n",ans[i]);
}