【[SCOI2012]喵星球上的点名】

好题啊

\(SA+ST\text{表}+\text{莫队}\)

我们先强行把所有的串连起来，串与串之间插入特殊字符，姓和名之间也插入特殊字符

之后跑一遍\(SA\)，求出\(sa\)和\(het\)

对于所有的询问串，我们标记好他们的开头，之后我们对于排好序的后缀建一个\(st\)表，找到每个询问串往左往右最多可以扩展到哪里

扩展到哪里自然是这个区间内的\(het\)的最小值大于等于询问串的长度了，这个二分+\(st\)表就能做到

第一问就变成了区间数颜色了，这个套上一个莫队就可以了

第二问是求出一种颜色被数了多少次，我们在莫队的时候顺便打上一个时间戳，如果在一个询问里这个颜色第一次出现我们就标记好这个询问的时间，等到下一次这个颜色被完全删除的时候我们利用这个操作的时间做一个差就好了

代码

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define maxn 500005

#define re register

#define LL long long

#define lowbit(x) ((x)&(-x))

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();re int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int tax[maxn],rk[maxn],sa[maxn],het[maxn],tp[maxn],f[maxn],S[maxn];

int to[maxn],c[maxn],St[maxn][19],logg[maxn],Ans[maxn],li[maxn],cnt[maxn];

int n,m,L,M,len,sz,ans;

inline void qsort()

{

	for(re int i=0;i<=M;i++) tax[i]=0;

	for(re int i=1;i<=L;i++) tax[rk[i]]++;

	for(re int i=1;i<=M;i++) tax[i]+=tax[i-1];

	for(re int i=L;i;--i) sa[tax[rk[tp[i]]]--]=tp[i];

}

struct Ask{int x,y,rk;} a[maxn];

inline void add(int x,int o) {if(!f[sa[x]]) return;if(!cnt[f[sa[x]]]) ++ans,c[f[sa[x]]]+=m-o+1;cnt[f[sa[x]]]++;}

inline void del(int x,int o) {if(!f[sa[x]]) return;cnt[f[sa[x]]]--;if(!cnt[f[sa[x]]]) --ans,c[f[sa[x]]]-=m-o+1;}

inline int query(int l,int r){int k=logg[r-l+1];return min(St[l][k],St[r-(1<<k)+1][k]);}

inline int cmp(Ask A,Ask B) { if(A.x/sz==B.x/sz) return A.y<B.y; return A.x<B.x;}

int main()

{

	n=read(),m=read();

	for(re int i=1;i<=n;i++)

	{

		len=read();

		for(re int j=1;j<=len;j++) S[++L]=read()+1,f[L]=i; S[++L]=0;

		len=read();

		for(re int j=1;j<=len;j++) S[++L]=read()+1,f[L]=i; S[++L]=0;

	}

	for(re int i=1;i<=m;i++)

	{

		len=read();to[i]=L+1;li[i]=len;

		for(re int j=1;j<=len;j++) S[++L]=read()+1; S[++L]=0;

	}

	for(re int i=1;i<=L;i++) M=max(M,S[i]);sz=M;

	for(re int i=1;i<=L;i++) if(!S[i]) S[i]=++sz;

	for(re int i=1;i<=L;i++) M=max(M,S[i]),rk[i]=S[i],tp[i]=i;

	qsort();

	for(re int w=1,p=0;p<L;M=p,w<<=1)

	{

		p=0;

		for(re int i=1;i<=w;i++) tp[++p]=L-w+i;

		for(re int i=1;i<=L;i++) if(sa[i]>w) tp[++p]=sa[i]-w;

		qsort();

		for(re int i=1;i<=L;i++) std::swap(rk[i],tp[i]);

		rk[sa[1]]=p=1;

		for(re int i=2;i<=L;i++)

			rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;

	}

	int k=0;

	for(re int i=1;i<=L;i++)

	{

		if(k) --k; int j=sa[rk[i]-1];

		while(S[i+k]==S[j+k]) ++k; het[rk[i]]=k;

	}

	memset(St,20,sizeof(St));

	for(re int i=1;i<=L;i++) St[i][0]=het[i];

	for(re int i=2;i<=L;i++) logg[i]=1+logg[i>>1];

	for(re int j=1;j<=18;j++)

		for(re int i=1;i+(1<<j)-1<=L;i++)

			St[i][j]=min(St[i][j-1],St[i+(1<<(j-1))][j-1]);

	for(re int i=1;i<=m;i++)

	{

		int j=rk[to[i]];a[i].rk=i;

		int l=2,r=j;

		while(l<=r) {int mid=l+r>>1;if(query(mid,j)>=li[i]) a[i].x=mid-1,r=mid-1;else l=mid+1;}

		if(!a[i].x) a[i].x=j;

		l=j+1,r=L;

		while(l<=r) {int mid=l+r>>1;if(query(j+1,mid)>=li[i]) a[i].y=mid,l=mid+1;else r=mid-1;}

		if(!a[i].y) a[i].y=j;

	}

	sz=std::sqrt(L);

	std::sort(a+1,a+m+1,cmp);

	int l=0,r=0;

	for(re int i=1;i<=m;i++)

	{

		while(l<a[i].x) del(l++,i);

		while(r<a[i].y) add(++r,i);

		while(l>a[i].x) add(--l,i);

		while(r>a[i].y) del(r--,i);

		Ans[a[i].rk]=ans;

	}

	for(re int i=1;i<=m;i++) printf("%d\n",Ans[i]);

	for(re int i=1;i<=n;i++) printf("%d ",c[i]);

	return 0;

}

巴特西

【[SCOI2012]喵星球上的点名】

最新文章

热门文章