反正先求一遍sa
然后这个问题可以稍微转化一下
默认比较A、B数组中元素的大小都是比较它们rank的大小，毕竟两个位置的LCP就是它们rank的rmq
然后每次只要求B[j]>=A[i]的LCP(B[j],A[i])，然后再求A[j]>B[i]的LCP(A[j],B[i])即可
这两个其实是差不多的，下面只说B[j]>=A[i]的怎么算
排序以后从后往前推着做（当然从前往后也行）
用一个权值线段树记下来LCP(A[i],B[j])==x的B[j]的数量、以及这个数量*x的和
然后考虑怎么把它从A[i]转移到A[i-1]
其实就是对于每个j给LCP(A[i],B[j])和LCP(A[i-1],A[i])取个min，放到权值线段树上，就是把大于LCP(A[i-1],A[i])的都删掉，然后在LCP(A[i-1],A[i])处加上刚才删掉的个数
所以我推着做的时候，先来取个min，然后把新来的B[j]加到线段树里，每做一个A[i]统计一下线段树整体的和即可
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=4e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,Q;
char s[maxn];
int sa[maxn],rnk[maxn],hei[maxn],rank1[maxn],tmp[maxn],cnt[maxn];
int st[maxn][]; inline void getsa(){
int i,j=,k;
for(i=;i<=N;i++) cnt[s[i]]=;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) rnk[i]=cnt[s[i]]; for(k=;j!=N;k<<=){
memset(cnt,,sizeof(cnt));
for(i=;i<=N;i++) cnt[rnk[i+k>N?:i+k]]++;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) tmp[cnt[rnk[i+k>N?:i+k]]--]=i;
memset(cnt,,sizeof(cnt));
for(i=;i<=N;i++) cnt[rnk[i]]++;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) sa[cnt[rnk[tmp[i]]]--]=tmp[i];
memcpy(rank1,rnk,sizeof(rank1));
rnk[sa[]]=j=;
for(i=;i<=N;i++){
if(rank1[sa[i]]!=rank1[sa[i-]]||rank1[sa[i]+k>N?:sa[i]+k]!=rank1[sa[i-]+k>N?:sa[i-]+k]) j++;
rnk[sa[i]]=j;
}M=j;
}
for(i=;i<=N;i++) sa[rnk[i]]=i;
} inline void geth(){
for(int i=,j=;i<=N;i++){
if(rnk[i]==) continue;
if(j) j--;
int x=sa[rnk[i]-];
while(x+j<=N&&i+j<=N&&s[x+j]==s[i+j]) j++;
hei[rnk[i]]=j;
}
} inline void getst(){
for(int i=N;i;i--){
st[i][]=hei[i];
for(int j=;st[i+(<<(j-))][j-];j++){
st[i][j]=min(st[i][j-],st[i+(<<(j-))][j-]);
}
}
} inline int rmq(int l,int r){
if(l>r) return N-sa[r]+;
int x=log2(r-l+);
return min(st[l][x],st[r-(<<x)+][x]);
} ll sum[maxn<<],siz[maxn<<];
bool laz[maxn<<]; inline void update(int p){sum[p]=sum[p<<]+sum[p<<|],siz[p]=siz[p<<]+siz[p<<|];}
inline void pushdown(int p){
if(!laz[p]) return;
int a=p<<,b=p<<|;
sum[a]=siz[a]=,laz[a]=;
sum[b]=siz[b]=,laz[b]=;
laz[p]=;
}
int erase(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
int re=siz[p];
siz[p]=sum[p]=;laz[p]=;
pushdown(p);
return re;
}else{
pushdown(p);
int m=l+r>>,re=;
if(x<=m) re=erase(p<<,l,m,x,y);
if(y>=m+) re+=erase(p<<|,m+,r,x,y);
update(p);
return re;
}
}
void add(int p,int l,int r,int x,int y){
if(l==r){
siz[p]+=y,sum[p]+=1ll*y*l;
}else{
pushdown(p);
int m=l+r>>;
if(x<=m) add(p<<,l,m,x,y);
else add(p<<|,m+,r,x,y);
update(p);
}
} inline bool cmp(int a,int b){return rnk[a]<rnk[b];} int A[maxn],B[maxn];
ll solve(int k,int l){
sort(A+,A+k+,cmp);sort(B+,B+l+,cmp);
ll re=;
for(int i=k,j=l;i;i--){
if(i!=k){
int x=rmq(rnk[A[i]]+,rnk[A[i+]]),t=erase(,,N,x+,N);
add(,,N,x,t);
}
for(;rnk[B[j]]>=rnk[A[i]]&&j;j--)
add(,,N,rmq(rnk[A[i]]+,rnk[B[j]]),);
re+=sum[];
}
erase(,,N,,N);
for(int i=k,j=l;j;j--){
if(j!=l){
int x=rmq(rnk[B[j]]+,rnk[B[j+]]),t=erase(,,N,x+,N);
add(,,N,x,t);
}
for(;rnk[A[i]]>rnk[B[j]]&&i;i--)
add(,,N,rmq(rnk[B[j]]+,rnk[A[i]]),);
re+=sum[];
}
erase(,,N,,N);
return re;
} int main(){
//freopen(".in","r",stdin);
int i,j,k;
N=rd(),Q=rd();
scanf("%s",s+);
M=;
getsa();geth();getst();
for(i=;i<=Q;i++){
int a=rd(),b=rd();
for(j=;j<=a;j++)
A[j]=rd();
for(j=;j<=b;j++)
B[j]=rd();
printf("%I64d\n",solve(a,b));
}
return ;
}