洛谷 P7879 -「SWTR-07」How to AK NOI?（后缀自动机+线段树维护矩乘）

洛谷题面传送门

orz 一发出题人（话说我 AC 这道题的时候，出题人好像就坐在我的右侧呢/cy/cy）

考虑一个很 naive 的 DP，\(dp_i\) 表示 \([l,i]\) 之间的字符串是否可以被识别，转移就枚举上一段的终止为止，然后 SAM/哈希判断子串是否在 \(s\) 中出现过。

注意到一个事实：所有长度 \(>2k\) 的字符串都可以由长度 \(\ge k\) 的字符串拼成，也就是说只有长度在 \([k,2k]\) 的字符串是有用的，故每次转移只用枚举 \(k+1\) 个转移点。注意到 \(k\) 的数据范围很小，因此我们可以考虑矩阵优化转移，即对于大小分别为 \(n\times m\) 和 \(m\times k\) 的矩阵 \(A,B\)，定义其乘积 \(C\) 满足 \(C_{i,j}=\text{or}_{t=1}^mA_{i,t}\land B_{t,j}\)，那么

\[\begin{bmatrix}
dp_{i}&dp_{i-1}&\cdots&dp_{i-2k+1}
\end{bmatrix}
=
\begin{bmatrix}
dp_{i-1}&dp_{i-2}&\cdots&dp_{i-2k}
\end{bmatrix}
\times
\begin{bmatrix}
g_1&1&0&0&\cdots&0\\
g_2&0&1&0&\cdots&0\\
g_3&0&0&1&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
g_{2k-1}&0&0&0&\cdots&1\\
g_{2k}&0&0&0&\cdots&0
\end{bmatrix}
\]

其中 \(g_j\) 表示 \([i-j+1,i]\) 是否为 \(s\) 的子串。

显然每次修改一个区间最多改变 \(r-l+1+2k\) 个位置的转移矩阵，因此我们有一个很自然的想法：线段树维护矩阵乘积，每次暴力修改线段树对应的位置的值，求一个位置的转移矩阵可用 SAM。查询就求一遍区间矩阵乘积，这样复杂度大概是 \((L+qk)·k^3\log n+qk^3\log n\)，显然无法通过，不过这里矩阵每个元素都是 0/1，因此可以用位运算加速实现 \(k^2\) 矩阵乘法，这样复杂度可达到 \((L+qk)·k^2\log n+qk^2\log n\)，还是无法通过。再观察到每次修改是一段区间，因此考虑对这一段区间上的叶子节点到根节点路径的并上的节点，重新计算它们转移矩阵的乘积，这样假设待重构的区间长度为 \(len\)，每次重构需要进行矩阵乘法的次数大概是 \(\sum\limits_{n}\lfloor\dfrac{len}{n}\rfloor=\mathcal O(len)\) 级别的，这样加号前面的 \(\log n\) 可以省去，复杂度就达到了 \((L+qk)·k^2+qk^2\log n\)，可以通过。

const int MAXN=3e6;

const int MAXM=3e5;

const int MAXP=6e6;

const int MAXK=16;

int n,m,k,qu;char s[MAXN+5],t[MAXM+5];

int ch[MAXP+5][9],len[MAXP+5],lnk[MAXP+5],cur=1,ncnt=1;

void extend(char c){

	int id=c-'a',nw=++ncnt,p=cur;

	len[nw]=len[cur]+1;cur=nw;

	while(p&&!ch[p][id]) ch[p][id]=nw,p=lnk[p];

	if(!p) return lnk[nw]=1,void();

	int q=ch[p][id];

	if(len[q]==len[p]+1) return lnk[nw]=q,void();

	int cl=++ncnt;len[cl]=len[p]+1;

	lnk[cl]=lnk[q];lnk[q]=lnk[nw]=cl;

	for(int i=0;i<9;i++) ch[cl][i]=ch[q][i];

	while(p&&ch[p][id]==q) ch[p][id]=cl,p=lnk[p];

}

struct mat{

	int a[MAXK+2];

	mat(){memset(a,0,sizeof(a));}

	mat operator *(const mat &rhs){

		mat res;

		for(int i=0;i<k*2;i++) for(int j=0;j<k*2;j++)

			if(a[i]>>j&1) res.a[i]|=rhs.a[j];

		return res;

	}

	void print(){

		for(int i=0;i<k+k;i++) for(int j=0;j<k+k;j++)

			printf("%d%c",a[i]>>j&1,"\0\n"[j==k+k-1]);

	}

};

int lf[MAXM+5],used[MAXM*4+5];

mat calc(int l){

	mat ret;

	for(int i=0;i+1<k+k;i++) ret.a[i]|=1<<i+1;

	int curp=1;

	for(int i=1;i<=min(l,k+k);i++){

		if(!ch[curp][t[l-i+1]-'a']) break;

		curp=ch[curp][t[l-i+1]-'a'];

		if(i>=k) ret.a[i-1]|=1;

	}

//	printf("calc %d\n",l);

//	ret.print();

	return ret;

}

namespace segtree{

	struct node{int l,r;mat v;} s[MAXM*4+5];

	void build(int k,int l,int r){

		s[k].l=l;s[k].r=r;

		if(l==r){s[k].v=calc(l),lf[l]=k;return;}

		int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);

		s[k].v=s[k<<1].v*s[k<<1|1].v;

	}

	void rebuild(int k){

		if(!used[k]) return;used[k]=0;

		if(s[k].l==s[k].r) return;

		rebuild(k<<1);rebuild(k<<1|1);

		s[k].v=s[k<<1].v*s[k<<1|1].v;

	}

	mat query(int k,int l,int r){

		if(l<=s[k].l&&s[k].r<=r) return s[k].v;

		int mid=s[k].l+s[k].r>>1;

		if(r<=mid) return query(k<<1,l,r);

		else if(l>mid) return query(k<<1|1,l,r);

		else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);

	}

}

void rebuild(int l,int r){

	static char buf[MAXM+5];scanf("%s",buf+1);

	for(int i=l;i<=r;i++) t[i]=buf[i-l+1];

	for(int i=l;i<=min(r+k+k,m);i++){

		for(int j=lf[i];j;j>>=1) used[j]=1;

		segtree::s[lf[i]].v=calc(i);

	} segtree::rebuild(1);

}

int main(){

//	freopen("passage.in","r",stdin);

//	freopen("passage.out","w",stdout);

	scanf("%*d%s%s%d%d",s+1,t+1,&k,&qu);

	n=strlen(s+1);m=strlen(t+1);

	for(int i=n;i;i--) extend(s[i]);

	segtree::build(1,1,m);

	while(qu--){

		int opt;scanf("%d",&opt);

		if(opt==1){

			int l,r;scanf("%d%d",&l,&r);

			rebuild(l,r);

		} else {

			int l,r;scanf("%d%d",&l,&r);

			mat v=segtree::query(1,l,r);

			printf("%s\n",(v.a[0]&1)?"Yes":"No");

//			v.print();

		}

	}

	return 0;

}

洛谷 P7879 -「SWTR-07」How to AK NOI?（后缀自动机+线段树维护矩乘）的相关教程结束。