BZOJ 3879: SvT（字尾數組+單調棧）

題目連結

題解:

求出字尾數組，然後用單調棧求出該區間作為區間最小值時的左右邊界即可。

AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 5e5+50;
int n,Q,m=26;
int rk[MAXN],sa[MAXN],y[MAXN],c[MAXN],h[MAXN];
int lg[MAXN],dp[MAXN][20],w[MAXN];
int l[MAXN],r[MAXN],v[MAXN],st[MAXN];
char s[MAXN];
inline void Sort(){
    for(int i=1;i<=m;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[rk[y[i]]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[rk[y[i]]]--]=y[i];
}
inline void SA(){
    for(int i=1;i<=n;i++) rk[i]=s[i]-'a'+1,y[i]=i;
    Sort();
    for(int k=1;k<=n;k<<=1){
        int num = 0;
        for(int i=n-k+1;i<=n;i++) y[++num]=i;
        for(int i=1;i<=n;i++)
            if(sa[i]>k)
                y[++num]=sa[i]-k;
        Sort();
        swap(rk,y);
        num = rk[sa[1]] = 1;
        for(int i=2;i<=n;i++)
            rk[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k] ? num : ++num);
        if(num == n) break;
        m = num;
    }
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    int k = 0;
    for(int i=1;i<=n;i++){
        if(k) --k;
        int j = sa[rk[i]-1];
        while(s[i+k]==s[j+k]) ++k;
        h[rk[i]] = k;
    }
}
inline void RMQ_INIT(){
    lg[1]=0;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++) dp[i][0]=h[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
inline int Query(int l,int r){
    if(l==r) return n-l+1;
    int ll = rk[l]+1,rr = rk[r];
    int k = lg[rr-ll+1];
    return min(dp[ll][k],dp[rr-(1<<k)+1][k]);
}
inline bool cmp(int x,int y){
    return rk[x] < rk[y];
}
int main(){
    //freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
    scanf("%d%d",&n,&Q);
    scanf("%s",s+1);
    SA();
    RMQ_INIT();
    while(Q--){
        int op; scanf("%d",&op);
        for(int i=1;i<=op;i++) scanf("%d",&v[i]);
        sort(v+1,v+op+1,cmp);
        int sz = unique(v+1,v+op+1)-v-1;
        for(int i=1;i<sz;i++) w[i]=Query(v[i],v[i+1]);
        w[0]=w[sz]=-1;
        int top; LL ans = 0;
        st[0]=0; top=0;
        for(int i=1;i<sz;i++){
            while(w[st[top]] > w[i]) top--;
            l[i]=st[top];
            st[++top]=i;
        }
        st[0]=sz; top=0;
        for(int i=sz-1;i;i--){
            while(w[st[top]] >= w[i]) top--;
            r[i]=st[top];
            st[++top]=i;
        }
        for(int i=1;i<sz;i++)
            ans = (ans+1LL*w[i]*(i-l[i])*(r[i]-i));
        printf("%lld\n",ans);
    }
}