自动搬运

查看原文

来自洛谷，原作者为

	万弘 新生。

搬运于2025-08-24 22:33:54，当前版本为作者最后更新于2021-10-15 09:20:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$k$ 足够小是解题的关键.

$\text{Lemma 1:}$ 若存在方案,则至少有一种方案不选择长度超过 $2k$ 的串.

考虑长度超过 $2k$ 的串一定能拆成两个至少为 $k$ 的串即可.

考虑对每个 $T_i$ 处理出 $l_i$ 表示最大的 $l$ 使得 $T[i,i+l-1]$ 是 $S$ 的子串,而由L1,超过 $2k$ 时可以直接认为是 $2k$ .通过对 $S$ 建SAM,这部分复杂度是 $O(nk)$ .

对于询问,考虑从左往右匹配, $f(i)$ 表示 $T[l,i]$ 这个前缀能否匹配.对于 $T_i$ ,可以转移到 $[i+k-1,i+l_i-1]$ .

那么考虑类似动态dp,对 $i$ 构造矩阵

$$\begin{bmatrix} 0 & 0 & 0& \cdots &1& 1& 1&\cdots& 0&0\\ 1 & 0 & 0&\cdots& 0 & 0 & 0&\cdots & 0& 0\\ 0 & 1 & 0 &\cdots& 0 & 0 & 0&\cdots & 0& 0\\ \vdots\\ 0& 0 & 0&\cdots& 0 & 0 & 0 &\cdots & 1 &0 \end{bmatrix} $$

这效果还不如直接口述

口述一下就是,第一行 $[k-1,l_i-1]$ 这些是 $1$ 别的是0,第 $i(i>1)$ 行仅有第 $i-1$ 列是1.

原理很简单,要么转移到 $[i+k-1,i+l_i-1]$ 要么前移一步.

用线段树维护,每次暴力修改 $O(L)$ 个位置,复杂度是 $ O(L\log m\ \text{Mul}(2k)+q\log m\ \text{VMul}(2k)) $ ,其中 $\text{Mul}(2k)$ 表示大小为 $2k\times 2k$ 的矩阵乘法复杂度,本题中可以通过压位做到 $4k^2$ , $\text{VMul}$ 表示大小为 $1\times 2k$ 的行向量乘 $2k\times 2k$ 的矩阵的复杂度,可以压位做到 $2k$ .

或者用分块维护, $O(L\ \text{Mul}(2k)+q\sqrt m\ \text{VMul}(2k))$ .

或者用分块+线段树维护.

下面代码使用线段树,正确性和复杂度均正确,但仍需要一些常数优化,仅供参考.

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
typedef unsigned un;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
	return f*x;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
template<typename T> bool umin(T& a,T t){if(a>t)return a=t,1;return 0;}
template<typename T> bool umax(T& a,T t){if(a<t)return a=t,1;return 0;}
/**********/
const int MAXN = 6000011;
struct SAM
{
	int t[MAXN][9],pre[MAXN],len[MAXN],last,tot;
	SAM(){last=tot=1;}
	void extend(int w)
	{
		int pos=last,cur=++tot;
		len[cur]=len[pos]+1,last=cur;
		while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos];
		if(!pos){pre[cur]=1;return;}
		int nxt=t[pos][w];
		if(len[nxt]==len[pos]+1)pre[cur]=nxt;
		else
		{
			int tmp=++tot;
			len[tmp]=len[pos]+1,memcpy(t[tmp],t[nxt],sizeof t[nxt]);
			pre[tmp]=pre[nxt],pre[cur]=pre[nxt]=tmp;
			while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos];
		}
	}
}sam;
struct Bmatrix
{
	un a[16];
	Bmatrix(){memset(a,0,sizeof a);}
	Bmatrix(un* tp){memcpy(a,tp,sizeof a);}
	inline Bmatrix operator* (const Bmatrix& you)
	{
		static un tp[16];
		memset(tp,0,sizeof tp);
		for(int i=0;i<16;++i)
			for(int k=0;k<16;++k)
				if(a[i]&(1u<<k))tp[i]|=you.a[k];
		return tp;
	}
	void see()
	{
		puts("See:");
		for(int i=0;i<16;++i)
		{
			for(int j=0;j<16;++j)printf("%d",a[i]>>j&1);
			puts("");
		}
	}
}a[200011];
int lf[200011];
Bmatrix getmat(int s,int t)
{
	static un tp[16];
	memset(tp,0,sizeof tp);
	if(s<=t)tp[0]=((1u<<(t+1))-1)^((1u<<s)-1);
	for(int i=1;i<16;++i)tp[i]=1u<<(i-1);
	return tp;
}
int n;
struct Segment_Tree
{
	static const int MAXN = 200011;
	Bmatrix t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
	void init(un l=1,un r=n,un num=1)
	{
		if(l==r){rt=a[l];return;}
		un mid=(l+r)>>1;
		init(l,mid,num<<1),init(mid+1,r,num<<1|1);
		rt=tl*tr;
	}
	void modify(un pos,un l=1,un r=n,un num=1)
	{
		if(l==r){rt=a[l];return;}
		un mid=(l+r)>>1;
		if(pos<=mid)modify(pos,l,mid,num<<1);
		else modify(pos,mid+1,r,num<<1|1);
		rt=tl*tr;
	}
	un res;
	void Query(un ql,un qr,un l=1,un r=n,un num=1)
	{
		if(ql<=l&&r<=qr)
		{
			//printf("[%u,%u]\n",l,r);
			//rt.see();
			un f=0;
			for(int i=0;i<16;++i)
				if(res&(1u<<i))f|=rt.a[i];
			res=f;
			return;
		}
		un mid=(l+r)>>1;
		if(ql<=mid)Query(ql,qr,l,mid,num<<1);
		if(qr>mid)Query(ql,qr,mid+1,r,num<<1|1);
	}
}sgt;
char s[MAXN],t[200011];
int main()
{
	int tasknumber=read();
	scanf("%s%s",s+1,t+1);
	int k=read(),q=read();
	int sn=strlen(s+1);
	for(int i=1;i<=sn;++i)sam.extend(s[i]-'a');
	n=strlen(t+1);
	for(int i=1;i<=n;++i)
	{
		int u=1,j=0;
		for(;j<k+k&&i+j<=n;++j)
		{
			u=sam.t[u][t[i+j]-'a'];
			if(!u)break;
		}
		a[i]=getmat(k-1,j-1);
		lf[i]=j;
		//a[i].see();
	}
	sgt.init();
	while(q--)
	{
		int op=read();
		if(op==1)
		{
			int l=read(),r=read();
			char pre=t[r+1];
			scanf("%s",t+l);
			t[r+1]=pre;
			for(int i=max(1,l-k-k);i<=r;++i)
			{
				int u=1,j=0;
				for(;j<k+k&&i+j<=n;++j)
				{
					u=sam.t[u][t[i+j]-'a'];
					if(!u)break;
				}
				if(j!=lf[i])a[i]=getmat(k-1,j-1),lf[i]=j,sgt.modify(i);
			}
		}
		else
		{
			int l=read(),r=read();
			sgt.res=1;
			sgt.Query(l,r);
			puts(sgt.res&1?"Yes":"No");
		}
	}
	return 0;
}