【链接】

【题意】

给你一个长度为n的字符串以及m个询问。

每个询问询问你所给的一些后缀,所有任意两个后缀之间的lcp的总和;

n<=5*10^5

∑t<=3*10^6

【题解】

按照这些后缀的rank值升序排

->利用Sa数组

即输入一个x,x--;

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

cmp-> return rank[a] < rank[b];

t = unique(a+1,a+1+t) - a - 1;

然后把lcp(a[i-1],a[i])求出来作为b[i-1];

然后对b用单调队列的方法。

统计答案就可以啦。

很简答的。。

【错的次数】

【反思】

在这了写反思

【代码】

#include
    
     using namespace std;const int N = 5e5;const int MAX_CHAR = 255;//每个数字的最大值。char s[N + 10];//如果是数字,就写成int s[N+10]就好,从0开始存int Sa[N + 10], T1[N + 10], T2[N + 10], C[N+10];int Height[N + 10], Rank[N + 10];void build_Sa(int n, int m) {	int i, *x = T1, *y = T2;	for (i = 0; i
     
      = 0; i--) Sa[--C[x[i]]] = i;	for (int k = 1; k <= n; k <<= 1)	{		int p = 0;		for (i = n - k; i
      
       = k) y[p++] = Sa[i] - k;		for (i = 0; i
       
        = 0; i--) Sa[--C[x[y[i]]]] = y[i];		swap(x, y);		p = 1; x[Sa[0]] = 0;		for (i = 1; i
        
         = n) break;		m = p;	}}void getHeight(int n){	int i, j, k = 0;	for (i = 1; i <= n; i++) Rank[Sa[i]] = i;	for (i = 0; i
         
          <= MAXL;i++) { pre2[i] = pre2[i-1]<<1; } need[1] = 0; need[2] = 1; int temp = 2; for (int i = 3; i <= n; i++)//need[i]表示长度为i是2的多少次方,可以理解为[log2i] if (pre2[temp] == i) need[i] = need[i - 1] + 1, temp++; else need[i] = need[i - 1]; } void getst(int *a,int n) { memset(fmax,-INF,sizeof fmax); memset(fmin,INF,sizeof fmin); for (int i = 1;i <= n;i++)//下标从0开始就改成对应的就好 fmax[i][0] = fmin[i][0] = a[i]; for (int l = 1;pre2[l]<=n;l++) for (int i = 1;i <= n;i++) if (i+pre2[l]-1<=n) fmax[i][l] = max(fmax[i][l-1],fmax[i+pre2[l-1]][l-1]); for (int l = 1;pre2[l]<=n;l++) for (int i = 1;i <= n;i++) if (i+pre2[l]-1<=n) fmin[i][l] = min(fmin[i][l-1],fmin[i+pre2[l-1]][l-1]); } int getmin(int l,int r) { int len = need[r-l+1]; return min(fmin[l][len],fmin[r-pre2[len]+1][len]); } int getmax(int l,int r) { int len = need[r-l+1]; return max(fmax[l][len],fmax[r-pre2[len]+1][len]); }}ST;const int NN =3e6;int a[NN+10],b[NN+10];int dl[NN+10],num[NN+10],tail;bool cmp(int x,int y){ return Rank[x] < Rank[y];}int main() { //freopen("F:\\rush.txt","r",stdin); int n,Q; scanf("%d%d",&n,&Q); scanf("%s", s); s[n] = 0; build_Sa(n + 1, MAX_CHAR);//注意调用n+1 getHeight(n); //处理一下rmq方便获取lcp ST.init(n); ST.getst(Height,n); while (Q--)//输入询问 { int t; scanf("%d",&t); for (int i = 1;i <= t;i++) { scanf("%d",&a[i]); a[i]--; } //排序、去重 sort(a+1,a+1+t,cmp);//按照Rank升序排 t = unique(a+1,a+1+t) - a - 1; for (int i = 1;i < t;i++) b[i] = ST.getmin(Rank[a[i]]+1,Rank[a[i+1]]);//获取它们之间的lcp tail = 0; long long ans = 0,temp = 0; for (int i = 1;i < t;i++) { int cnt = 0; while (tail > 0 && dl[tail] > b[i]) { cnt += num[tail]; temp -= 1LL*dl[tail]*num[tail]; temp += 1LL*b[i]*num[tail]; tail--; } temp += b[i]; dl[++tail] = b[i]; num[tail] = cnt + 1; ans += temp; } printf("%lld\n",ans); } return 0;}