BZOJ 3828 Criminal

Link

对我来说算神题了

Solution

先考虑暴力做法 枚举每个与模式串的最后一个颜色相同的点，判断是否合法。 判断方法是从这个点向两边分别贪心地匹配两个模式串，找到一个最靠右的左串匹配位置$l$，和最靠左的右串匹配位置$r$。然后在$[1,l-1]$和$[r+1,n]$中找一下是否有两个颜色相同的点。至于找相同，一种方法就是遍历$[1,l-1]$，把途径的颜色用bool[]标记，然后再遍历$[r+1,n]$。 可以看出，这样又做了很多无用功，因为很有可能连续的一段区间，向左右匹配的位置都是相同的。这样就不好了。 所以考虑对这个量进行预处理。然后我就怎么也想不出来了。研究一番Claris巨神的代码，并看不懂复杂度。写完A掉之后，忽然灵光一现，不禁拍案叫绝。 设原序列为$c[]$，左模式串的序列为$x[]$。假设当前在计算$ls[]$，$ls[i]$表示使得$c[]$的$[a,i-1]$中存在一个子序列$x[]$，且最大的$a$，设$first[p]$表示在$c[]$中的第一个颜色$p$的位置，$next[i]$表示序列$c[]$中下一个与$c[i]$颜色相同的位置。 外层循环从$[1,n]$枚举$c[]$的每一个位置$i$，设$f[p]$表示使得$[a,i-1]$能成功匹配$x[p..x.length]$的最大的$a$。 然后循环这样做： (在代码中，$lx==x.length-1$)

for(int i=1;i<=n;++i) {
    ls[i]=f[1];
    if(c[i]==x[lx]) {
        f[lx]=i;
        for(int u,p=lx-1;p;--p) {
            if((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]) {
                do f[p]=u;
                while((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]);
            } else
                break;
        }
    }
}

如果$x[]$的倒数第二个字符与$c[i]$相同，那就更新$f[lx]$。然后$p$从$lx-1$开始枚举，将$f[p]$挪到最后一个在$f[p+1]$之前的颜色为$x[p]$的位置。 复杂度？ 设$x[p]$在$c[]$中出现了$t[x[p]]$次，那么$f[p]$至多会向后移动$t$次。而$x[]$的元素互异，那么复杂度就是$O(\sum t[x[i]])=O(n)$ 处理出来之后，可以发现，随着枚举点$i$右移，$ls[i]$和$rs[i]$都是单调不降的。因此可以类比莫队，实现$O(n)$计算。 记得特判模式串为$1$的情况

Tips

唯有泪千行。。 KMP--一个指针的均摊--$O(n)$ 双指针--两个指针的均摊--$O(n)$ K指针--K个指针的均摊--$O(n)$ 只注意到了匹配的第一个点位置的单调性，但没有进一步观察所有点位置的单调性

Code

#include "lucida"
const int MAXN=1000000+11;
using std::reverse;
int K;
void Calc(int c[],int n,int x[],int lx,int ls[]) {
	//处理出 ls[i] 表示i左边的最靠右的匹配
	static int f[MAXN],next[MAXN],first[MAXN];
	if(!lx) {
		for(int i=1;i<=n;++i)
			ls[i]=i;
	} else {
		for(int i=1;i<=K;++i)
			first[i]=n+1;
		for(int i=n;i>=1;--i) {
			next[i]=first[c[i]];
			first[c[i]]=i;
			f[i]=0;
		}
		for(int i=1;i<=n;++i) {
			ls[i]=f[1];
			if(c[i]==x[lx]) {
				f[lx]=i;
				for(int u,p=lx-1;p;--p) {
					if((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]) {
						do f[p]=u;
						while((u=(f[p]?next[f[p]]:first[x[p]]))<f[p+1]);
					} else
						break;
				}
			}
		}
	}
}

int cnt,val[MAXN][2],n;
void Modify(int pos,int d,int v) {
	if(pos==0 || pos==n+1)
		return;
	val[pos][d]+=v;
	if(v>0 && val[pos][d]==1 && val[pos][d^1])
		cnt++;
	if(v<0 && val[pos][d]==0 && val[pos][d^1])
		cnt--;
}
int main() {
//	freopen("input","r",stdin);
	static int Ans[MAXN],x[MAXN],y[MAXN],c[MAXN],ls[MAXN],rs[MAXN];
	int ac=0,lx,ly;is>>n>>K;
	for(int i=1;i<=n;++i) is>>c[i];
	is>>lx>>ly;
	for(int i=1;i<=lx;++i) is>>x[i];
	for(int i=1;i<=ly;++i) is>>y[i];
	Calc(c,n,x,lx-1,ls);
	reverse(c+1,c+1+n);
	Calc(c,n,y,ly-1,rs);
	reverse(c+1,c+1+n);
	reverse(rs+1,rs+1+n);
	for(int i=1;i<=n;++i) rs[i]=n-rs[i]+1;
	for(int p=1;p<ls[1];++p) 
		Modify(c[p],0,1);
	for(int p=rs[1]+1;p<=n;++p) 
		Modify(c[p],1,1);
	if(c[1]==x[lx] && cnt)
		Ans[++ac]=1;
	
	for(int i=2;i<=n;++i) {
		for(int p=ls[i-1];p<=ls[i]-1;++p)
			Modify(c[p],0,1);
		for(int p=rs[i-1]+1;p<=rs[i];++p)
			Modify(c[p],1,-1);
		if(c[i]==x[lx] && cnt)
			Ans[++ac]=i;
	}
	os<<ac<<'\n';
	for(int i=1;i<=ac;++i)
		os<<Ans[i]<<(i==ac?"":" ");
	//os<<'\n';
	return 0;
}
/*
 * Wa 没有特判1 
 */