【题解】洛谷 P7879 「SWTR-07」How to AK NOI? | 20211011 模拟赛 读文章（passage）【线段树 矩阵快速幂 压位 SAM】

题目链接

题目链接

题意

给定串 (s,t)，定义集合 (S) 为 (s) 中所有长度不小于 (k) 的子串，多次修改 (t) 的一个区间，多次询问 (s) 的一个区间能否由 (S) 中的串拼起来。(|s|leq 3 imes 10^6,|t|leq 2 imes 10^5,qleq 10^5)，修改的区间长度之和 (leq 3 imes 10^5)，(kleq 8)，4s，(|sigma|leq 9)。

题解

我们只需要考虑长度小于 (2k) 的子串，因此我们可以 DP，记录近 (2k) 个位置能否凑出来。将转移写作矩阵，利用位运算优化到 (O(k^2)) 的乘法，线段树维护矩阵乘。此外需要一个后缀自动机检查一个串是不是某字符串的子串。

#include<bits/stdc++.h>
using namespace std;
int getint(){ int x;scanf("%d",&x);return x; }
const int N=3e6+10,M=2e5+10,K=16;
char beg_mem;
int n,m,k,kk;
struct mat{
	int v[K];
};
mat operator*(const mat &a,const mat &b){
	mat bT,c;
	memset(&bT,0,sizeof(bT));
	memset(&c,0,sizeof(c));
	for(int i=0;i<kk;i++)
		for(int j=0;j<kk;j++)
			bT.v[i]|=((b.v[j]>>i)&1)<<j;
	for(int i=0;i<kk;i++)
		for(int j=0;j<kk;j++)
			c.v[i]|=(bool(a.v[i]&bT.v[j]))<<j;
	return c;
}

mat mt[M];
mat sgt[M<<2];
void update(int l,int r,int x,int nl,int nr){
	if(nr<l||nl>r)return;
	if(nl==nr){
		sgt[x]=mt[nl];
		return;
	}
	int mid=nl+nr>>1;
	update(l,r,x<<1,nl,mid);
	update(l,r,x<<1|1,mid+1,nr);
	sgt[x]=sgt[x<<1|1]*sgt[x<<1];
}
mat ans;
void query(int l,int r,int x,int nl,int nr){
	if(x==1){
		for(int i=0;i<kk;i++)ans.v[i]=1<<i;
	}
	if(nr<l||nl>r)return;
	if(l<=nl&&nr<=r){
		ans=ans*sgt[x];
		return;
	}
	int mid=nl+nr>>1;
	query(l,r,x<<1|1,mid+1,nr);
	query(l,r,x<<1,nl,mid);
}

struct node{
    int ch[10],len,fa;
    int sz;
};
node sam[N<<1];
int cnt=0,lst=0;

void extend(char c){
    int cur=++cnt;
    sam[cur].len=sam[lst].len+1;
    sam[cur].sz=1;
    for(;lst!=-1&&sam[lst].ch[c-'a']==-1;lst=sam[lst].fa) sam[lst].ch[c-'a']=cur;
    if(lst==-1) sam[cur].fa=0;
    else{
        int q=sam[lst].ch[c-'a'];
        if(sam[q].len==sam[lst].len+1)sam[cur].fa=q;
        else{
            int clone=++cnt;
            memcpy(sam+clone,sam+q,sizeof(node));
			sam[clone].sz=0;
			sam[clone].len=sam[lst].len+1;
			sam[cur].fa=sam[q].fa=clone;
			for(;sam[lst].ch[c-'a']==q;lst=sam[lst].fa)
				sam[lst].ch[c-'a']=clone;
        }
    }
    lst=cur;
}

char s[N],t[M];
void update(int x){
	mt[x].v[0]=0;
	long long hsh=0;
	int u=0;
	for(int i=0;i<kk&&x-i;i++){
		u=sam[u].ch[t[x-i]-'a'];
		if(u==-1)break;
		if(i>=k-1)
			mt[x].v[0]|=1<<i;
	}
}

char tmp[M];
char end_mem;
int main(){
//	freopen("P7879_49.in","r",stdin);
//	freopen("P7879_49.my.out","w",stdout);
//	cerr<<".";
	int subt=getint();
	scanf("%s",s+1);
	scanf("%s",t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	k=getint();
	kk=k+k;
//	cerr<<"/";
    memset(sam,-1,sizeof(sam));
    sam[0].len=0;
	for(int i=n;i;i--)
		extend(s[i]);

//	cerr<<"/";
	for(int x=1;x<=m;x++){
		update(x);
		for(int i=1;i<kk;i++)
			mt[x].v[i]=1<<(i-1);
	}
//	cerr<<"/";
	
	update(1,m,1,1,m);
	int q=getint();
	while(q--){
		int op=getint(),l=getint(),r=getint();
		if(op==1){
			scanf("%s",tmp);
			for(int i=0;i<r-l+1;i++)
				t[l+i]=tmp[i];
			int ul=l,ur=min(m,r+kk);
			for(int i=ul;i<=ur;i++)
				update(i);
			update(ul,ur,1,1,m);
		}else{
			query(l,r,1,1,m);
			puts(ans.v[0]&1?"Yes":"No");
		}
	}
}