【链接】h在这里写链接
【题意】
给你一个长度为n的字符串以及m个询问。
每个询问询问你所给的一些后缀,所有任意两个后缀之间的lcp的总和;
n<=5*10^5
∑t<=3*10^6
每个询问询问你所给的一些后缀,所有任意两个后缀之间的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用单调队列的方法。
统计答案就可以啦。
很简答的。。
->利用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用单调队列的方法。
统计答案就可以啦。
很简答的。。
【错的次数】
0
【反思】
在这了写反思
【代码】
#include<bits/stdc++.h>
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<m; i++) C[i] = 0;for (i = 0; i<n; i++) C[x[i] = s[i]]++;for (i = 1; i<m; i++) C[i] += C[i - 1];for (i = n - 1; i >= 0; i--) Sa[--C[x[i]]] = i;for (int k = 1; k <= n; k <<= 1){int p = 0;for (i = n - k; i<n; i++) y[p++] = i;for (i = 0; i<n; i++) if (Sa[i] >= k) y[p++] = Sa[i] - k;for (i = 0; i<m; i++) C[i] = 0;for (i = 0; i<n; i++) C[x[y[i]]]++;for (i = 1; i<m; i++) C[i] += C[i - 1];for (i = n - 1; i >= 0; i--) Sa[--C[x[y[i]]]] = y[i];swap(x, y);p = 1; x[Sa[0]] = 0;for (i = 1; i<n; i++)x[Sa[i]] = y[Sa[i - 1]] == y[Sa[i]] && y[Sa[i - 1] + k] == y[Sa[i] + k] ? p - 1 : p++;if (p >= 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<n; i++) {if (k) k--;j = Sa[Rank[i] - 1];while (s[i + k] == s[j + k]) k++;Height[Rank[i]] = k;}
}const int MAXL = 19;//log2数组的最大长度
const int INF = 0x3f3f3f3f;//数值绝对值的最大值struct abc{int pre2[MAXL+5],need[N+10];int fmax[N+10][MAXL+5],fmin[N+10][MAXL+5];void init(int n){pre2[0] = 1;for (int i = 1;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++;elseneed[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+1getHeight(n);//处理一下rmq方便获取lcpST.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]]);//获取它们之间的lcptail = 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;
}
