[SCOI2012]喵星球上的点名（树状数组+后缀数组）

我们把所有的名，姓，询问都拼起来构成一个新的长串，然后跑一边SA。排完序后对于每一个询问，我们可以二分求出它所对应的区间（即满足这个区间的前缀都是这个询问串）。然后问题就转化为很多区间问区间出现过的不同的数。这个东西可以用离线后吧询问按右端点从小到大排序+树状数组解决（HH的项链，采花）。

那么第二问该怎么办，每一个询问我们把这个区间+1，我们考虑每一个节点的贡献，就是当前点的权值减去上一个和这个点对应字符串相同点的权值（没扫到一个区间的右端点就要把这个区间-1）。

代码巨丑

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1010000;

typedef pair<int,int> p;

vector<p> vec[N];

vector<int> vec1[N];

int c[N],x[N],s[N],sa[N],rk[N],height[N],y[N],n,m;

int mn[N][20],tn,tm,pre[N],col[N],len[N],vis[N],L[N],R[N],tr[N],ans[N],anss[N],num,last[N];

void get_sa(){

	for(int i=1;i<=n;i++)c[x[i]=s[i]]++;

	for(int i=1;i<=m;i++)c[i]+=c[i-1];

	for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;

	for(int k=1;k<=n;k<<=1){

		int num=0;

		for(int i=n-k+1;i<=n;i++)y[++num]=i;

		for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;

		for(int i=1;i<=m;i++)c[i]=0;

		for(int i=1;i<=n;i++)c[x[i]]++;

		for(int i=1;i<=m;i++)c[i]+=c[i-1];

		for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;

		for(int i=1;i<=n;i++)swap(x[i],y[i]);

		num=1;x[sa[1]]=1;

		for(int i=2;i<=n;i++)

			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;

		if(n==num)break;

		m=num;

	}

}

void get_height(){

	int k=0;

	for(int i=1;i<=n;i++)rk[sa[i]]=i;

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

		if(rk[i]==1)continue;

		if(k)k--;

		int j=sa[rk[i]-1];

		while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;

		height[rk[i]]=k;

	}

}

void pre_work(){

	for(int i=1;i<=n;i++)mn[i][0]=height[i];

	int len=log2(n);

	for(int j=1;j<=len;j++)

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

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

}

int getmn(int l,int r){

	int len=log2(r-l+1);

	return min(mn[l][len],mn[r-(1<<len)+1][len]);

}

int lowbit(int x){

	return x&-x;

}

void add(int x,int w){

	if(x==0)return;

	for(int i=x;i<=n;i+=lowbit(i))tr[i]+=w;

}

int getsum(int x){

	int tmp=0;

	for(int i=x;i;i-=lowbit(i))tmp+=tr[i];

	return tmp;

}

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int main(){

	tn=read();tm=read();

	for(int i=1;i<=tn;i++){

		int k=read();

		for(int j=1;j<=k;j++)s[++n]=read()+tm+tn,col[n]=i;

		s[++n]=-i+tm+tn;

		k=read();

		for(int j=1;j<=k;j++)s[++n]=read()+tm+tn,col[n]=i;

		s[++n]=-i+tm+tn;

	}

	for(int i=1;i<=tm;i++){

		len[i]=read();

		vis[n+1]=i;

		for(int j=1;j<=len[i];j++){

			s[++n]=read()+tm+tn;

		}

		s[++n]=-i-tn+tm+tn;

	}

	m=220000;

	get_sa();

	get_height();

	pre_work();

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

		if(vis[sa[i]]){

			int l=i+1,r=n;

			int ans=i;

			while(l<=r){

				int mid=(l+r)>>1;

				if(getmn(i+1,mid)>=len[vis[sa[i]]]){

					l=mid+1;

					ans=mid;

				}

				else r=mid-1;

			}

			vec[ans].push_back(make_pair(i,vis[sa[i]]));

			L[++num]=i;R[num]=ans+1;

		}

		if(col[sa[i]]){

			pre[i]=last[col[sa[i]]];

			last[col[sa[i]]]=i;

		}

	}

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

		if(col[sa[i]]){

			add(pre[i],-1);

			add(i,1);

		}

		if(vec[i].size())for(int j=0;j<vec[i].size();j++)

			ans[vec[i][j].second]=getsum(i)-getsum(vec[i][j].first-1);

	}

	for(int i=1;i<=tm;i++)printf("%d\n",ans[i]);

	memset(tr,0,sizeof(tr));

	for(int i=1;i<=num;i++)add(L[i],1),add(R[i],-1),vec1[R[i]].push_back(L[i]);

	for(int j=1;j<=n;j++){

		for(int i=0;i<vec1[j].size();i++)

			add(vec1[j][i],-1),add(j,1);

		anss[col[sa[j]]]+=getsum(j)-getsum(pre[j]);

	}

	for(int i=1;i<=tn;i++)printf("%d ",anss[i]);

	return 0;

}

巴特西

[SCOI2012]喵星球上的点名（树状数组+后缀数组）

最新文章

热门文章