Description
给定 \(N\) 个姓名串和 \(M\) 个点名串。询问每个点名串点到了多少姓名和每个姓名串被点到了几次。\(N\leq 5\cdot 10^4,M\leq 10^5\)。
Sol
卡了我一周90分的题原来是数组开小我就艹了我就
最开始以为是 \(AC\) 自动机裸题但是细想了一下发现并不会，还是老老实实想 \(SA\) 。
首先要把这些串连在一起，然后跑一遍 \(SA\) ，可以先求出每个点名串到底点到了多少姓名串（也就是说在 \(SA\) 上有多少位置和点名串的 \(LCP\) 是点名串自己），发现这个在 \(SA\) 上是一段区间，可以二分左右端点求出。时间复杂度 \(O(n\log n)\)。
然后这两问分别考虑，第一问就相当于区间数颜色，可以离线+树状数组解决。就是按照区间右端点排序，如果当前的值 \(a[i]=x\)，那就在 \(i\) 处 \(+1\)，在 \(x\) 上一次出现的位置 \(las[x]\) 处 \(-1\)。然后统计区间 \([L,R]\) 直接树状数组上查就好了。这个算法的核心思路是保证相同数字的贡献只有 \(1\)，也就是说每个颜色只会在前缀和数组中出现 \(1\) 次。这部分时间复杂度 \(O(n\log n)\)。
第二问就是求每个颜色被几个不同的区间覆盖了。这个同样离线，对于一个区间 \([L,R]\)，我们在扫到 \(L\) 位置的时候在 \(L\) 处 \(+1\)，扫到 \(R+1\) 的时候撤销 \(L\) 的 \(+1\) 操作。做到 \(i\) 位置的时候，设 \(a[i]=x\)，记录 \(x\) 上一次出现的位置 \(las[x]\)，那 \(ans[x]\) 就要加上 \((las[x],i]\) 的和。正确性就是如果一个区间覆盖了某个数，肯定会在左端点之后第一个出现这个数的位置统计上答案。这里的时间复杂度也是 \(O(n\log n)\)。
Code
这道题写的是真的丑...
把压行的都改掉了发现还是丑...
#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=1e6+5;
const int M=1e4+5;
// wtf?????
// 把m开大就过了？？？？？？？
// 卡了老子一周的狗题？？？？
int ans[N],ans2[N],st[N][20],fs[N],len[N];
int s[N],tot,sa[N],rk[N],height[N],lg[N],f[N];
int n,m,num,x[N],y[N],c[N],belong[N][2],las[N];//belong=2 refers to question
struct Ques{
int l,r,idx;
friend bool operator<(Ques a,Ques b){
return a.r<b.r;
}
}ques[N];
struct qu{
int type,x;
qu(){}
qu(int a,int b){type=a,x=b;}
};
std::vector<qu> v[N];
void add(int *f,int x,int y){
while(x<=tot)
f[x]+=y,x+=x&-x;
}
int query(int *f,int x){
int now=0;
while(x) now+=f[x],x-=x&-x;
return now;
}
void getsa(int m=100001){
for(int i=1;i<=tot;i++) c[x[i]=s[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=tot;i;i--) sa[c[x[i]]--]=i;
for(int k=1;num=0,k<=tot;k<<=1){
for(int i=tot-k+1;i<=tot;i++) y[++num]=i;
for(int i=1;i<=tot;i++) if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=0;i<=m;i++) c[i]=0;
for(int i=1;i<=tot;i++) c[x[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=tot;i;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y),x[sa[1]]=num=1;
for(int i=2;i<=tot;i++) x[sa[i]]=y[sa[i]]==y[sa[i-1]] and y[sa[i]+k]==y[sa[i-1]+k]?num:++num;
if(num==tot) return;m=num;
}
}
void getheight(int k=0){
for(int i=1;i<=tot;i++)
rk[sa[i]]=i;
for(int i=1;i<=tot;i++){
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(i+k<=tot and j+k<=tot and s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
}
void getst(){
for(int i=2;i<=tot;i++)
lg[i]=lg[i-1]+((1<<lg[i-1]+1)==i);
for(int i=1;i<=tot;i++)
st[i][0]=height[i];
for(int k=1;k<=lg[tot];k++)
for(int i=1;i+(1<<k)-1<=tot;i++)
st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]);
}
int getint(){
int X=0,w=0;char ch=getchar();
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
int query(int x,int y){
if(x==y) return tot-sa[x]+1;
if(x>y) swap(x,y);x++;
int k=lg[y-x+1];
return min(st[x][k],st[y-(1<<k)+1][k]);
}
signed main(){
n=getint(),m=getint();int cnt=10001;
for(int i=1;i<=n;i++){
if(i!=1)
s[++tot]=++cnt;
int lenn=getint();
for(int j=1;j<=lenn;j++)
s[++tot]=getint()+1,belong[tot][0]=1,belong[tot][1]=i;
s[++tot]=++cnt;
lenn=getint();
for(int j=1;j<=lenn;j++)
s[++tot]=getint()+1,belong[tot][0]=1,belong[tot][1]=i;
}
for(int i=1;i<=m;i++){
s[++tot]=++cnt;
len[i]=getint();fs[i]=tot+1;
for(int j=1;j<=len[i];j++)
s[++tot]=getint()+1,belong[tot][0]=2,belong[tot][1]=i;
}
getsa(),getheight(),getst();
for(int i=1;i<=m;i++){
//rk[fs[i]]
int l=1,r=rk[fs[i]],now=0;
while(l<=r){
int mid=l+r>>1;
if(query(mid,rk[fs[i]])>=len[i]) now=mid,r=mid-1;
else l=mid+1;
}
ques[i].l=now;l=rk[fs[i]],r=tot,now=0;
while(l<=r){
int mid=l+r>>1;
if(query(rk[fs[i]],mid)>=len[i]) now=mid,l=mid+1;
else r=mid-1;
}
ques[i].r=now;ques[i].idx=i;
}
std::sort(ques+1,ques+1+m);int ptr=1;
for(int i=1;i<=tot;i++){
if(belong[sa[i]][0]==1 and las[belong[sa[i]][1]])
add(f,las[belong[sa[i]][1]],-1);
if(belong[sa[i]][0]==1)
add(f,i,1),las[belong[sa[i]][1]]=i;
while(ptr<=m and ques[ptr].r==i){
ans[ques[ptr].idx]=query(f,ques[ptr].r)-query(f,ques[ptr].l-1);
ptr++;
}
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
memset(f,0,sizeof f);memset(las,0,sizeof las);
for(int i=1;i<=m;i++)
v[ques[i].l].pb(qu(1,ques[i].l)),v[ques[i].r].pb(qu(-1,ques[i].l));
for(int i=1;i<=tot;i++){
for(auto x:v[i])
if(x.type==1)
add(f,x.x,x.type);
if(belong[sa[i]][0]==1)
ans2[belong[sa[i]][1]]+=query(f,i)-query(f,las[belong[sa[i]][1]]);
if(belong[sa[i]][0]==1)
las[belong[sa[i]][1]]=i;
for(auto x:v[i])
if(x.type==-1)
add(f,x.x,x.type);
} for(int i=1;i<=n;i++)
printf("%d%c",ans2[i],i==n?'\n':' ');
return 0;
}