【LOJ#2507】[CEOI2011]Matching（KMP，树状数组）

题面

题解

发现要做的是排名串的匹配。

然后我们考虑把它转成这个位置之前有多少个数小于当前这个数，这样子只要每个位置都对应相等那么一定是合法的。

然后就可以类似\(KMP\)的预处理出一个\(nxt\)数组，然后再类似\(KMP\)的匹配。

因为需要支持动态求前面一段区间有多少个数比这个数小，所以需要用\(BIT\)维护。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 1000100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

vector<int> Ans;

int c[MAX],N,n,m,a[MAX],S[MAX],p[MAX],nt[MAX],rk[MAX];

int lb(int x){return x&(-x);}

void Add(int x,int w){while(x<=N)c[x]+=w,x+=lb(x);}

int getsum(int x){int s=0;while(x)s+=c[x],x-=lb(x);return s;}

int main()

{

	n=read();m=read();N=n;

	for(int i=1;i<=n;++i)p[read()]=i;

	for(int i=1;i<=m;++i)S[i]=a[i]=read();

	sort(&S[1],&S[m+1]);

	for(int i=1;i<=m;++i)a[i]=lower_bound(&S[1],&S[m+1],a[i])-S;

	for(int i=1;i<=n;++i)Add(p[i],1),rk[i]=getsum(p[i]);

	memset(c,0,sizeof(c));

	nt[0]=nt[1]=0;

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

	{

		int t=nt[i-1];

		while(t&&getsum(p[i])+1!=rk[t+1])

		{

			int v=nt[t];

			while(lst<i-v)Add(p[lst++],-1);

			t=v;

		}

		if(getsum(p[i])+1==rk[t+1])++t;

		nt[i]=t;Add(p[i],1);

	}

	memset(c,0,sizeof(c));N=m;

	for(int i=1,j=0,lst=1;i<=m;++i)

	{

		while(j&&getsum(a[i])+1!=rk[j+1])

		{

			int v=nt[j];

			while(lst<i-v)Add(a[lst++],-1);

			j=v;

		}

		if(getsum(a[i])+1==rk[j+1])++j;

		if(j==n)

		{

			Ans.push_back(i-n+1);int v=nt[j];

			while(lst<i-v+1)Add(a[lst++],-1);

			j=v;

		}

		Add(a[i],1);

	}

	printf("%d\n",(int)Ans.size());

	for(int v:Ans)printf("%d ",v);puts("");

	return 0;

}

巴特西

【LOJ#2507】[CEOI2011]Matching（KMP，树状数组）

【LOJ#2507】[CEOI2011]Matching（KMP，树状数组）

题面

题解

最新文章

热门文章