题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2754
网上大神们的正解都是用AC自动机，蒟蒻不会写AC自动机，只能后缀数组硬着头皮上了。（网上绝大多数后缀数组解法都存在被卡TLE的可能（n^2暴力枚举串），找不到完整详细的解释跟代码，蒟蒻只能来发发解法秀秀下限了）：
首先，就是把所有名字和姓和点名串串在一起（之间加一个不可能出现的数，如负无穷之类的），然后做一次后缀数组，求出height[],sa[],rank[]，那么，以点名串为前缀的后缀在sa[]中必定是一段连续的区间出现，然后对于第1个问题，就转化为了查询区间中不同的数（同属一个姓名的后缀认为是同一个数）的个数的问题，第二个问题，就转化成了，某一个数被多少个不同的区间覆盖的问题，这两个问题我实在想不出在线解法，只能用离散化+BIT维护来写。
对于第一个问题：参见“BZOJ-1878: [SDOI2009]HH的项链”的解法，我就懒得码字了，来个大神们的题解：传送门（http://www.dxmtb.com/blog/diff/）
对于第二个问题，首先，用类似基数排序的方法对区间进行离散化：
设数组t[]为基数排序中的桶，对于每一个区间[l,r],加入t[l],然后做标记A，再加入t[r+1]，做标记B；
对于每一个后缀数组中的后缀i，如果该后缀属于某一个姓名，预处理出在该后缀前面的第一个属于同一个单词的后缀last[i],如果不存在，设last[i]=0。
然后，从1到L(后缀数组长度)扫一遍，如果当前在位置i，首先处理完t[i]里面加入的所有区间，设该区间为[l,r],若该区间被标记A标记，则在树状数组执行对l位置+1的操作，若被标记B标记，则在树状数组中执行对l位置-1的操作，然后如果该后缀属于某一姓名，则对于该姓名的答案+Sum(last[i]+1,i)，直到整个数组处理完毕，这是所有答案也就处理完成了。
复杂度：
倍增算法求后缀数组：O(L log L)
离线处理问题一：O(n log n + L)
离线处理问题二：O(n log n +L)
总复杂度：O(L log L + n log n)
这样，在理论复杂度上就可以过全部数据了。
可怜我在BZOJ上跑得比暴力还慢。。。不过大数据确实可以在2s内过，而且卡不了。
5366d0160924ab18b54e6f3a37fae6cd7b890b66.jpg.png
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define lowbit(x)((-x)&x)
#define MAXN 20010
#define MAXM 50010
#define MAXL 500010
#define inf 0x7fffffff
#define MAXD 21
int s[MAXL],name[MAXL];
int n,m,lenn[MAXN],lenm[MAXM],firn[MAXN],firm[MAXM],N=0;
int getstring() {
int len;
scanf("%d",&len);
for (int i=0;i++<len;) scanf("%d",&name[i]);
return len;
}
int sa[MAXL],rank[MAXL],r[MAXL],w[MAXL],x[MAXL],y[MAXL],height[MAXL],b,Nn;
struct saver {
int v,t;
} c[MAXL];
bool cmp(saver x,saver y) {
return x.v<y.v;
}
void Make_sa() {
for (int i=0;i++<N;) c[i].v=s[i],c[i].t=i;
sort(c+1,c+N+1,cmp);
Nn=0;
for (int i=0;i++<N;) {
if (i==1||c[i].v!=c[i-1].v) Nn++;
rank[c[i].t]=Nn;
}
b=1;
x[sa[0]=0]=y[0]=-1;
do {
for (int i=0;i++<N;) x[i]=rank[i],y[i]=i+b<=N?rank[i+b]:0;
b<<=1;
for (int i=0;i<=N;i++) w[i]=0;
for (int i=0;i++<N;) w[y[i]]++;
for (int i=0;i++<N;) w[i]+=w[i-1];
for (int i=0;i++<N;) r[w[y[i]]--]=i;
for (int i=0;i<=N;i++) w[i]=0;
for (int i=0;i++<N;) w[x[r[i]]]++;
for (int i=0;i++<N;) w[i]+=w[i-1];
for (int i=N;i;i--) sa[w[x[r[i]]]--]=r[i];
Nn=0;
for (int i=0;i++<N;) {
if (x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]) Nn++;
rank[sa[i]]=Nn;
}
} while (Nn<N);
int k=0;
for (int i=0;i++<N;) {
k=max(k-1,0);
height[rank[i]]=k;
for (int j=k;i+j<=N&&sa[rank[i]-1]+j<=N&&s[i+j]==s[sa[rank[i]-1]+j];j++) height[rank[i]]++;
k=height[rank[i]];
}
}
int st[MAXL][MAXD];
void Init_st() {
for (int i=0;i++<N;) st[i][0]=height[i];
int d=int(log2(N))+1;
for (int i=0;i++<d;) {
for (int j=0;j++<N;) {
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int Min(int l,int r) {
int k=int(log2(r-l+1));
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int ansn[MAXN],ansm[MAXM],left[MAXM],right[MAXM];
struct node {
node *next;
int l,r,t;
bool flag;
} *head[MAXL];
void Insert(int w,int l,int r,int t,bool flag) {
node *p=new(node);
p->next=head[w],p->l=l,p->r=r,p->t=t,p->flag=flag;
head[w]=p;
}
int next[MAXL],last[MAXL];
bool Cmp(int x,int y) {
return x<y;
}
struct Bit{
int t[MAXL],n;
void Init(int _n) {
memset(t,0,sizeof(t));
n=_n;
}
void Add(int x,int y) {
for (;x<=n;x+=lowbit(x)) t[x]+=y;
}
int Sum(int x) {
int rec=0;
for (;x;x-=lowbit(x)) rec+=t[x];
return rec;
}
} bit;
void Solve0() {
memset(head,0,sizeof(head));
for (int i=0;i++<m;) Insert(left[i],left[i],right[i],i,true);
memset(next,0,sizeof(next));
memset(last,0,sizeof(last));
memset(w,0,sizeof(w));
bit.Init(N);
for (int i=0;i++<n;) {
for (int j=0;j<lenn[i];j++) r[j]=rank[firn[i]+j];
sort(r,r+lenn[i],Cmp);
bit.Add(r[0],1);
for (int j=0;j<lenn[i]-1;j++) next[r[j]]=r[j+1];
for (int j=1;j<lenn[i];j++) last[r[j]]=r[j-1];
for (int j=0;j<lenn[i];j++) w[r[j]]=i;
}
for (int i=0;i++<N;) {
for (node *p=head[i];p;p=p->next) ansm[p->t]=bit.Sum(p->r);
if (w[i]) bit.Add(i,-1);
if (next[i]) bit.Add(next[i],1);
}
}
void Solve1() {
memset(head,0,sizeof(head));
memset(ansn,0,sizeof(ansn));
for (int i=0;i++<m;) Insert(left[i],left[i],right[i],i,true),Insert(right[i]+1,left[i],right[i],i,false);
bit.Init(N);
for (int i=0;i<=N;i++) {
for (node *p=head[i];p;p=p->next) if (p->flag) bit.Add(p->l,1); else bit.Add(p->l,-1);
ansn[w[i]]+=bit.Sum(i)-bit.Sum(last[i]);
}
}
void Solve() {
Init_st();
for (int i=0;i++<m;) {
if (height[rank[firm[i]]]<lenm[i]) left[i]=rank[firm[i]]
; else {
int le=1,ri=rank[firm[i]];
while (ri-le>1) {
int mid=(le+ri)>>1;
if (Min(mid,rank[firm[i]])>=lenm[i]) ri=mid
; else le=mid;
}
left[i]=le;
}
if (height[rank[firm[i]]+1]<lenm[i]) right[i]=rank[firm[i]]
; else if (Min(rank[firm[i]]+1,N)>=lenm[i]) right[i]=N
; else {
int le=rank[firm[i]]+1,ri=N;
while (ri-le>1) {
int mid=(le+ri)>>1;
if (Min(rank[firm[i]]+1,mid)>=lenm[i]) le=mid
; else ri=mid;
}
right[i]=le;
}
}
Solve0();
Solve1();
}
int main() {
s[0]=inf-1;
scanf("%d%d",&n,&m);
for (int i=0;i++<n;) {
lenn[i]=getstring(),firn[i]=N+1;
for (int j=0;j++<lenn[i];) s[++N]=name[j];
int delta=getstring();
lenn[i]++,s[++N]=-inf;
for (int j=0;j++<delta;) s[++N]=name[j];
s[++N]=-inf;
lenn[i]+=delta;
}
for (int i=0;i++<m;) {
firm[i]=N+1,lenm[i]=getstring();
for (int j=0;j++<lenm[i];) s[++N]=name[j];
s[++N]=-inf;
}
Make_sa();
Solve();
for (int i=0;i++<m;) printf("%d\n",ansm[i]);
for (int i=0;i++<n-1;) printf("%d ",ansn[i]);
printf("%d\n",ansn[n]);
return 0;
}
网友评论