【BZOJ3879】SvT 后缀数组+单调栈

时间：2021-10-12 20:54:25

【BZOJ3879】SvT

Description

(我并不想告诉你题目名字是什么鬼)

有一个长度为n的仅包含小写字母的字符串S,下标范围为[1,n].

现在有若干组询问,对于每一个询问,我们给出若干个后缀(以其在S中出现的起始位置来表示),求这些后缀两两之间的LCP(LongestCommonPrefix)的长度之和.一对后缀之间的LCP长度仅统计一遍.

Input

第一行两个正整数n,m,分别表示S的长度以及询问的次数.

接下来一行有一个字符串S.

接下来有m组询问,对于每一组询问,均按照以下格式在一行内给出:

首先是一个整数t,表示共有多少个后缀.接下来t个整数分别表示t个后缀在字符串S中的出现位置.

Output

对于每一组询问,输出一行一个整数,表示该组询问的答案.由于答案可能很大,仅需要输出这个答案对于23333333333333333(一个巨大的质数)取模的余数.

Sample Input

7 3
popoqqq
1 4
2 3 5
4 1 2 5 6

Sample Output

0
0
2
Hint
样例解释:
对于询问一,只有一个后缀”oqqq”,因此答案为0.
对于询问二,有两个后缀”poqqq”以及”qqq”,两个后缀之间的LCP为0,因此答案为0.
对于询问三,有四个后缀”popoqqq”,”opoqqq”,”qqq”,”qq”,其中只有”qqq”,”qq”两个后缀之间的LCP不为0,且长度为2,因此答案为2.
对于100%的测试数据,有S<=5*10^5,且Σt<=3*10^6.
特别注意:由于另一世界线的某些参数发生了变化,对于一组询问,即使一个后缀出现了多次,也仅算一次.

题解：依旧是后缀数组+单调栈，跟差异那道题差不多，具体方法：

将给出的所有后缀按照rank排序，去重，然后用rmq查出相邻两个的LCP，现在问题转化成一个序列求两两间最小值，这又等价于对于序列中的每一个数，求它是哪些数对之间的最小值，这又等价于对于每一个数，求左边和右边第一个比它小的数，用单调栈轻松搞定。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define mod 23333333333333333ll

using namespace std;

const int maxn=500010;

int r[maxn],ra[maxn],rb[maxn],st[maxn],h[maxn],sa[maxn],rank[maxn];

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

int n,m,Q;

typedef long long ll;

ll ans;

char str[maxn];

void build()

{

	int i,j,k,p,*x=ra,*y=rb;

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

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

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

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

	{

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

		for(i=0;i<n;i++)	if(sa[i]>=j)	y[p++]=sa[i]-j;

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

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

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

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

		for(swap(x,y),x[sa[0]]=0,i=p=1;i<n;i++)

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

	}

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

	for(i=k=0;i<n-1;h[rank[i++]]=k)

		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

}

bool cmp(int a,int b)

{

	return rank[a]<rank[b];

}

int query(int a,int b)

{

	int k=Log[b-a+1];

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

}

int main()

{

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

	int i,j,a,b;

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

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

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

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

		for(i=1;i+(1<<j)-1<=n;i++)

			f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);

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

	for(i=1;i<=Q;i++)

	{

		scanf("%d",&a);

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

		{

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

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

			vis[v[j]]=1;

		}

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

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

		s[0]=s[a]=-1,q[1]=0,t=1;

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

		{

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

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

		}

		t=1,q[1]=a;

		for(j=a-1;j>0;j--)

		{

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

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

		}

		ans=0;

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

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

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

	}

	return 0;

}

相关文章