P7879 题解
万弘
·
·
题解
$ \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;
}
```