COCI2013-2014 Contest#1 F SLASTI?AR

其实挺妙的一个数据结构题

题意: 给定一个A串，对于查询的每个\(B\)串，从头开始匹配匹配\(A\)的每个后缀，每次匹配失败的代价是\(\text{LCP}+1\)可，匹配成功的代价是\(|B|\)，且立即停止，求代价总和

设\(A\)串长为\(n\)，查询个数为\(q\)，查询总长为\(m\)

我们知道求两个串的\(\text{LCP}\)可以把两个串中间放一个符号分开，跑后缀数组/后缀自动机

但是首先是\(m=3\cdot 10^6\)，内存就开不下

而且发现，如果\(|B|\)的某个前缀未出现在\(A\)中，后面的部分都不造成贡献，所以可以在\(A\)串中定位\(B\)的每个前缀

这样就只需要求\(A\)的后缀数组即可，然而，这个并不好实现

假设当前已经定位了一个长度为\(i\)的前缀，其对应的后缀位置排名为\(pos\)

显然可以\(\text{Sparse Table}\)+倍增求出\(pos\)在后缀数组上两边对应的\(LCP\ge d\)的后缀排名范围\([L_i,R_i]\)，这些后缀都是合法的

那么接下来就是在当前前缀上接上下一个字符\(c\)，这个如果再外加数据结构并不好实现

考虑后缀数组的性质，\([L_i,R_i]\)这些后缀前\(d\)个字符相同，\(d+1\)个字符呈单调非递减，所以可以二分这个字符\(c\)的位置

这样匹配\(pos\)和查询\([L_i,R_i]\)的复杂度均为\(\log n\)，这样就用\(O(m\log n)\)的复杂度完成了串定位

如果不考虑每次完成匹配后停止，其实答案就是\(\sum R_i-L_i+1\)，即\(\sum_i LCP_i=\sum_i \sum_j [LCP_j\ge i]\)

设最终的匹配位置为\(p\)，这个位置可以用线段树在最后的一段\([L_{|B|},R_{|B|}]\)中求最小值得到

考虑减掉多余的部分，即减去实际位置\(>p\)的且在后缀数组排名在\([L_i,R_i]\)中的部分

可以把所有的\([L_i,R_i]\)拿出来作为，离线询问，用树状数组维护查询，复杂度为\(O((n+m)\log n)\)

因此总复杂度为\(O((n+m)\log n)\)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#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)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }
 
const int N=1e5+10,M=3e6+10;
 
int n,m;
char s[3000000],t[N];
 
int rk[N<<1],tmp[N],cnt[N],sa[N],lcp[N];
int st[17][N],Log[N];
 
void Build(int n){
    rep(i,1,n) cnt[int(s[i])]++;
    rep(i,1,200) cnt[i]+=cnt[i-1];
    rep(i,1,n) rk[i]=cnt[(int)s[i]],sa[i]=i;
    for(reg int k=1;k<n;k<<=1) {
        for(reg int i=0;i<=n;++i) cnt[i]=0;
        for(reg int i=1;i<=n;++i) cnt[rk[i+k]]++;
        for(reg int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
        for(reg int i=n;i>=1;--i) tmp[cnt[rk[i+k]]--]=i;
 
        for(reg int i=0;i<=n;++i) cnt[i]=0;
        for(reg int i=1;i<=n;++i) cnt[rk[i]]++;
        for(reg int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
        for(reg int i=n;i>=1;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i];
 
        for(reg int i=1;i<=n;++i) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+k]!=rk[sa[i-1]+k]);
        for(reg int i=1;i<=n;++i) rk[i]=tmp[i];
    }
    int h=0;
    rep(i,1,n) {
        int j=sa[rk[i]-1];
        if(h) h--;
        while(s[i+h]==s[j+h]) h++;
        lcp[rk[i]-1]=h;
    }
    rep(i,2,N-1) Log[i]=Log[i>>1]+1;
    rep(i,1,n) st[0][i]=lcp[i];
    rep(i,1,Log[n]) {
        int len=1<<(i-1);
        rep(j,1,n-len) st[i][j]=min(st[i-1][j],st[i-1][j+len]);
    }
}
 
void Que(int &l,int &r,int d) {
    drep(i,Log[l],0) if(l-(1<<i)>=1 && st[i][l-(1<<i)]>=d) l-=1<<i;
    drep(i,Log[n-r],0) if(r+(1<<i)<=n && st[i][r]>=d) r+=1<<i;
}
int FindChar(int l,int r,int len,int c){
    int res=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(s[sa[mid]+len]<=c) l=mid+1,res=mid;
        else r=mid-1;
    }
    if(res==-1 || s[sa[res]+len]!=c) return 0;
    return res;
}
 
 
ll ans[N];
int ql[M],qr[M],qid[M],qnxt[M];
int head[N],qc;
int L[N],R[N];
 
struct BIT{
    int s[N];
    void Add(int p) { while(p<=n) s[p]++,p+=p&-p; }
    int Que(int p) {
        int res=0;
        while(p) res+=s[p],p-=p&-p;
        return res;
    }
    int Que(int l,int r){ return Que(r)-Que(l-1); }
} T;
struct Tree{
    int s[N<<2];
    void Build(int p,int l,int r){
        if(l==r) { s[p]=sa[l]; return ;}
        int mid=(l+r)>>1;
        Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
        s[p]=min(s[p<<1],s[p<<1|1]);
    }
    int Que(int p,int l,int r,int ql,int qr){
        if(ql<=l && r<=qr) return s[p];
        int mid=(l+r)>>1,res=1e9;
        if(ql<=mid) cmin(res,Que(p<<1,l,mid,ql,qr));
        if(qr>mid) cmin(res,Que(p<<1|1,mid+1,r,ql,qr));
        return res;
    }
}SGT;
 
 
 
int main(){
    scanf("%d%s",&n,s+1);
    Build(n),scanf("%d",&m);
    SGT.Build(1,1,n);
    rep(i,1,m) {
        scanf("%s",t+1);
        L[0]=1,R[0]=n;
        int pos=n,len=0;
        for(int j=1;t[j];++j) {
            L[len=j]=L[j-1],R[j]=R[j-1];
            pos=FindChar(L[j],R[j],j-1,t[j]);
            if(!pos) break;
            Que(L[j]=pos,R[j]=pos,j);
            ans[i]+=R[j]-L[j]+1;
        }
        if(pos && (pos=SGT.Que(1,1,n,L[len],R[len]))<n) {
            ans[i]+=pos-1,pos++;
            rep(j,1,len){
                qc++,ql[qc]=L[j],qr[qc]=R[j],qid[qc]=i,qnxt[qc]=head[pos];
                head[pos]=qc;
            }
        } else ans[i]+=n;
    }
    drep(i,n,1){
        T.Add(rk[i]);
        for(int j=head[i];j;j=qnxt[j]) ans[qid[j]]-=T.Que(ql[j],qr[j]);
    }
    rep(i,1,m) printf("%lld\n",ans[i]);
}

COCI2013-2014 Contest#1 F SLASTI?AR

原文：https://www.cnblogs.com/chasedeath/p/13598123.html