bzoj3879

题解：

后缀数组

然后把读入的内容去重，按照ｒａｎｋ排序

然后用单调栈处理一下

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

const ll M=23333333333333333ll;

int r[N],ra[N],rb[N],a,st[N],h[N],sa[N],rank[N],n,m,Q;

int q[N],t,ls[N],rs[N],f[N][],Log[N],vis[N],v[N],s[N];

ll ans;

char str[N];

void build()

{

    int *x=ra,*y=rb;

    for (int i=;i<n;i++)st[x[i]=r[i]]++;

    for (int i=;i<m;i++)st[i]+=st[i-];

    for (int i=n-;i>=;i--)  sa[--st[x[i]]]=i;

    for (int j=,p=;p<n;j<<=,m=p)

     {

         p=;

        for (int i=n-j;i<n;i++)y[p++]=i;

        for (int i=;i<n;i++)

         if (sa[i]>=j)y[p++]=sa[i]-j;

        for (int i=;i<m;i++)st[i]=;

        for (int i=;i<n;i++)st[x[y[i]]]++;

        for (int i=;i<m;i++)st[i]+=st[i-];

        for (int i=n-;i>=;i--)sa[--st[x[y[i]]]]=y[i];

        swap(x,y);x[sa[]]=;

        for (int i=p=;i<n;i++)

         x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+j]==y[sa[i-]+j])?p-:p++;

     }

    for (int i=;i<n;i++)rank[sa[i]]=i;

    for (int i=,k=;i<n-;h[rank[i++]]=k)

     {

         if (k)k--;

         for (int j=sa[rank[i]-];r[i+k]==r[j+k];k++);

     }

}

int cmp(int a,int b){return rank[a]<rank[b];}

int query(int a,int b)

{

    int k=Log[b-a+];

    return min(f[a][k],f[b-(<<k)+][k]);

}

int main()

{

    scanf("%d%d%s",&n,&Q,str);

    for (int i=;i<n;i++)r[i]=str[i]-'a'+;

    n++;m=;build();n--;

    for (int i=;i<=n;i++)f[i][]=h[i];

    for (int j=;(<<j)<n;j++)

     for (int i=;i+(<<j)-<=n;i++)f[i][j]=min(f[i][j-],f[i+(<<j-)][j-]);

    for (int i=;i<=n;i++)Log[i]=Log[i>>]+;

    while (Q--)

     {

        scanf("%d",&a);

        for (int j=;j<=a;j++)

         {

            scanf("%d",&v[j]);

            v[j]--;

            if (vis[v[j]])j--,a--;

            vis[v[j]]=;

         }

        sort(v+,v+a+,cmp);

        for (int j=;j<a;j++)s[j]=query(rank[v[j]]+,rank[v[j+]]);

        s[]=s[a]=-;q[]=;t=;

        for (int j=;j<a;j++)

         {

            while (t&&s[q[t]]>s[j])t--;

            ls[j]=q[t],q[++t]=j;

         }

        t=,q[]=a;

        for (int j=a-;j>;j--)

         {

            while (t&&s[q[t]]>=s[j])t--;

            rs[j]=q[t],q[++t]=j;

         }

        ans=;

        for (int j=;j<a;j++)ans=(ans+(ll)(j-ls[j])*(rs[j]-j)*s[j])%M;

        printf("%lld\n",ans);

        for (int j=;j<=a;j++)vis[v[j]]=;

     }

}