1 条题解

  • 0
    @ 2025-8-24 22:12:24

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Alex_Wei
    **

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

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

    以下是正文

    题目传送门。

    题意简述：给定长度为 nn 的文本串 aa 和有 mm 个单词的字典 sis_i。qq 次操作，每次求出字典内所有单词在 a[l,r]a[l,r] 的出现次数，或将 a[l,r]a[l,r] 替换为 tt 不断重复的结果。

    n,∑∣t∣≤106n,\sum |t|\leq10^6，m,q≤105m,q\leq 10^5，∣s∣≤50|s|\leq 50，∑∣si∣≤2×105\sum |s_i|\leq 2\times 10^5。

    假设没有修改操作，且 m=1m=1，即字典中只有一个单词，记该单词长度为 LL。 一个自然的想法是可以求出对于每个位置 ii，a[i−L+1,i]a[i-L+1,i] 是否匹配 s1s_1，记为 fi (f1,f2,⋯ ,fL−1=0)f_i\ (f_1,f_2,\cdots,f_{L-1}=0)，暴力匹配即可。

    查询时，因为 [l,l],[l,l+1],⋯ ,[l,l+L−2][l,l],[l,l+1],\cdots,[l,l+L-2] 长度不够，显然无法匹配 s1s_1，又因为 [x−L+1,x] (x≥l+L−1)[x-L+1,x]\ (x\geq l+L-1) 匹配时不受小于 ll 的位置的影响，即不会因为 a[1,l−1]a[1,l-1] 消失而导致 [x−L+1,x][x-L+1,x] 的匹配情况改变（由于 x≥l+L−1x\geq l+L-1，所以 x−L+1≥lx-L+1\geq l）。因此直接查询 ∑j=xrfj\sum_{j=x}^rf_j 即可。直接前缀和维护可以做到 O(q+nL)\mathcal{O}(q+nL)，使用 KMP 可以优化到 O(q+n)\mathcal{O}(q+n)。

    Subtask #3：如果有修改操作呢？事情就变得无比麻烦了。昨天尝试写了一下，甚至比正解还难写（doge）。

    首先得处理这个循环的 tt。当然，我不知道怎么处理，所以看了眼 s_r_f 的题解。 注意到题目中说 “与文件相比，单词的长度是非常小的（L≤50L\leq 50）”，那么就好好利用一下这个性质。

    首先，f[l,l+L−2]f_{[l,l+L-2]} 肯定是没有什么好方法，只能暴力硬做，那么，这一部分的想法是：从 l−L+1l-L+1 开始跑 KMP，匹配到 l+L−2l+L-2 并暴力更新 f[l,l+L−2]f_{[l,l+L-2]} 即可。为什么要从 l−L+1l-L+1 而不是 ll 开始跑：flf_l 是与 al−L+1a_{l-L+1} 有关的，所以从 ll 开始跑会导致 f[l,l+L−2]f_{[l,l+L-2]} 全为 00，这显然是错误的。

    同样的，对于 f[r+1,r+L−1]f_{[r+1,r+L-1]}，从 r−L+2r-L+2 开始跑 KMP，一直匹配到 r+L−1r+L-1 并暴力更新 f[r+1,r+L−1]f_{[r+1,r+L-1]} 即可。

    接下来处理中间那一大坨循环的 tt，记其长度为 TT。有一个并不显然但很好理解，同时也是最关键的性质：修改过后，fi=fi+T (l+L−1≤i≤r−T+1)f_i=f_{i+T}\ (l+L-1\leq i\leq r-T+1)，也就是这部分 ff 会产生长度为 TT 的循环节。根据题目所给条件，有 a[i,i−L+1]=a[i+T,(i+T)−L+1]a_{[i,i-L+1]}=a_{[i+T,(i+T)-L+1]}（ii 的范围同上），所以显然。因此，求出循环节并用线段树维护即可。

    当然，说起来简单，还有很多需要注意的地方：

    • Q1：如何维护循环节？

      A1：一个循环节信息主要就是循环节的开头位置，长度和循环节内每个位置的值。 因此，需要维护每一个循环节 idid（表示这是第 idid 次修改形成的循环节）的开头位置 lpidlp_{id}，长度 lenidlen_{id}，以及每一个位置 ii 上的值 did,id_{id,i}。循环节内位置从 00 开始标号。

      在线段树区间 [l,r][l,r] 的懒标记内维护两个信息：idid 和 hdhd。idid 表示该标记是第 idid 次修改形成的循环节（不是第 idid 个循环节），hdhd 表示该区间的起始位置 ll 在该循环节中的位置。

      在 pushdown 的时候，假设我们传入了三个参数 l,r,xl,r,x 表示从区间 [l,r][l,r] 下传，该区间在线段树内编号为 xx。先求出左区间和右区间的分界点 m=⌊l+r2⌋m=\lfloor\frac{l+r}{2}\rfloor，再求出右区间 [m+1,r][m+1,r] 的起始位置 m+1m+1 在循环节的位置，记为 midmid，则不难求出 mid=(hd+(m+1)−l) mod lenidmid=(hd+(m+1)-l)\bmod len_{id}，然后将 id,hdid,hd 与 id,midid,mid 的懒标记分别赋给 [l,m][l,m] 与 [m+1,r][m+1,r]，并更新其维护的区间 ff 之和：

        void push(int l,int r,int x){ // pushdown
  	if(laz[x].id){
  		int m=l+r>>1;
  		int id=laz[x].id,hd=laz[x].hd;
  		int mid=(hd+(m-l+1))%len[id];
  		mark(l,m,x<<1,id,hd);
  		mark(m+1,r,x<<1|1,id,mid);
  		val[x]=val[x<<1]+val[x<<1|1];
  		laz[x].id=0;
  	}
  }

      其中 mark(l,r,x,id,hd) 表示给在线段树内编号为 xx 的区间 [l,r][l,r] 打上 id,hdid,hd 的懒标记。此时我们求出该区间末位置在循环节 idid 中的位置 tl=(hd+(r−l)) mod lenidtl=(hd+(r-l))\bmod len_{id}，并求出 [l,r][l,r] 间共有多少个循环节 idid，然后更新即可。

       void mark(int l,int r,int x,int id,int hd){ // mark lazytag & update
  	laz[x]={id,hd};
  	int ori=l-hd,tl=(r-ori)%len[id],rid=(r-ori)/len[id];
  	if(rid==0)val[x]=pre[id][tl]-(hd?pre[id][hd-1]:0);
  	else val[x]=pre[id][tl]+(rid*sum[id]-(hd?pre[id][hd-1]:0));
  }

      一些代码说明：oriori 表示 ll 所在的循环节的开头，并假设其为第 00 个循环节。ridrid 表示 rr 在第 ridrid 个循环节内。需要注意的是，这里的 preid,ipre_{id,i} 是 preidpre_{id} 的前缀和。sumidsum_{id} 表示循环节 idid 所有位置上的和，即 sumid=preid,lenid−1sum_{id}=pre_{id,len_{id}-1}。

    • Q2：暴力匹配时怎么求出 aa 当前的内容？

      首先，需要求出的 aa 是一段区间，设其为 [l,r][l,r]。那么在线段树上按序遍历每一个区间 [x,x] (l≤x≤r)[x,x]\ (l\leq x\leq r)。具体来说，就算当前区间 [l′,r′]⊆[l,r][l',r']\subseteq[l,r] 也不返回，直到访问到叶子结点 [x,x][x,x]。可以证明这样访问的时间复杂度为 O(log⁡n+len)\mathcal{O}(\log n+len)。又因为需要求出的长度不超过 2L2L，因此总时间复杂度为 O(q(log⁡n+L))\mathcal{O}(q(\log n+L))。

      若该区间有标记 id,hdid,hd，那么该位置上的字符应为 tid,hdt_{id,hd}，即第 idid 次修改时给出的字符串 tidt_{id} 的第 hdhd 个位置上的字符。否则该位置上的字符应为 axa_x。

        void forms(int l,int r,int ql,int qr,int x){ // form current string [ql,qr]
  	if(ql>qr)return;
  	if(l==r){
  		if(laz[x].id)tmp+=qt[laz[x].id][laz[x].hd];
  		else tmp+=ct[l-1];
  		return;
  	} int m=l+r>>1; push(l,r,x);
  	if(ql<=m)forms(l,m,ql,qr,x<<1);
  	if(m<qr)forms(m+1,r,ql,qr,x<<1|1);
  }

    • Q3：暴力匹配求出 ff 后怎么在线段树上修改？

      A3：同样，需要更新的 ff 也是一段区间 [l,r][l,r]。如法炮制，按序遍历每一个区间 [x,x] (l≤x≤r)[x,x]\ (l\leq x\leq r)，并修改 ff 的值即可。

      由于求出 aa 的内容时需要每个节点的标记，而暴力修改 ff 的位置有的需要打标记，如 [l,l+L−2][l,l+L-2]，有的不需要，如 [r+1,r+L−1][r+1,r+L-1]，所以需要分情况讨论。

        void modifyc(int l,int r,int ql,int qr,int x,bool tg){ // brute force : change
  	if(ql>qr)return;
  	if(l==r){
  		val[x]=f[l];
  		if(tg)laz[x]={id,(l-lpos)%len[id]};
  		return;
  	} int m=l+r>>1; push(l,r,x);
  	if(ql<=m)modifyc(l,m,ql,qr,x<<1,tg);
  	if(m<qr)modifyc(m+1,r,ql,qr,x<<1|1,tg);
  	val[x]=val[x<<1]+val[x<<1|1];
  }

    还有一些注意点（踩过的坑）：

    • 正如 s_r_f 所说，为了使代码更简洁，我们可以将左边暴力匹配的区间 [l−L+1,l+L−2][l-L+1,l+L-2] 的右端点向右稍微移动一点，使得新的右端点 ledled 刚好是一段循环节的结尾。同时，为了求出循环节，还要再向右匹配 TT 个位置。
    • 如果区间的长度太小，可以直接暴力匹配。
    • 需要先求出 sumidsum_{id} 再更新，因为更新时需要用到 sumidsum_{id}。

    这样，时间复杂度为 (q(log⁡n+L)+∑T)\mathcal(q(\log n+L)+\sum T)。

    看到这里，你可能以为我已经讲完了。实际上并没有，这只是 m=1m=1 的部分分。不过别担心，只要你会 AC 自动机，那么 mm 为多少都不是问题。

    注意到字典是固定的，所以我们对其建立 AC 自动机。那么只需要将 fif_i 的定义改为：将 a[1,i]a[1,i] 放在 AC 自动机上跑到的位置 pp 在 fail 树上与根节点之间的路径所包含的终止节点个数 valpval_p。即 $val_p=\sum_{i=1}^m [endpos_i\in \mathrm{path}(p,root)]$。一个套路的方法是将所有终止节点在 fail 树上的子树的 valval 值 +1+1，这样可以 O(1)\mathcal{O}(1) 求 fif_i。如果不理解上述方法，P5357，请。

    注意到 fif_i 定义中的 a[1,i]a[1,i] 可以改成 a[i−L+1,i] (L=max⁡∣sj∣)a[i-L+1,i]\ (L=\max|s_j|)，因为任何一个单词 sjs_j 与 aa 在位置 ii 的匹配情况不会受到 ax (x≤i−L)a_x\ (x\leq i-L) 的影响（最长的单词与 aa 在位置 ii 的匹配的第一个位置为 i−L+1i-L+1）。

    剩下来就和 m=1m=1 几乎一模一样，只不过在暴力匹配时的方式从跑 KMP 变成了跑 AC 自动机。总时间复杂度 O(∑∣si∣+∑∣ti∣+q(log⁡n+L))\mathcal{O}(\sum|s_i|+\sum|t_i|+q(\log n+L))，其中 L=max⁡∣si∣L=\max |s_i|。

    /*
	Powered by C++11.
	Author : Alex_Wei.
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=1e6+5;
const int L=50+5;
const int Q=1e5+5;
const int S=2e5+5;

// basic variables
int lc,nw,q;
ll mp[1<<7],f[N];
string ct;

struct ACAM{
	int cnt,son[S][62],fa[S],val[S];
	void ins(string s){
		int p=0;
		for(char it:s){
			if(!son[p][mp[it]])son[p][mp[it]]=++cnt;
			p=son[p][mp[it]];
		} val[p]++;
	} void build(){
		queue <int> q;
		for(int i=0;i<62;i++)if(son[0][i])q.push(son[0][i]);
		while(!q.empty()){
			int t=q.front(); q.pop();
			for(int i=0;i<62;i++)
				if(son[t][i])fa[son[t][i]]=son[fa[t]][i],q.push(son[t][i]);
				else son[t][i]=son[fa[t]][i];
			val[t]+=val[fa[t]];
		}
	} void run(){ // get f
		int p=0;
		for(int i=1;i<=lc;i++)f[i]=val[p=son[p][mp[ct[i-1]]]];
	}
}ac;

// query variables
ll id,len[Q],sum[Q];
vector <ll> pre[Q];
string qt[Q];

// lazytag & Segment Tree
string tmp;
struct lazy{
	int id,hd;
}; struct SegTree{
	ll val[N<<2],lpos;
	lazy laz[N<<2];
	void build(int l,int r,int x){
		if(l==r){
			val[x]=f[l];
			return;
		} int m=l+r>>1;
		build(l,m,x<<1),build(m+1,r,x<<1|1);
		val[x]=val[x<<1]+val[x<<1|1];
	} void mark(int l,int r,int x,int id,int hd){ // mark lazytag & update
		laz[x]={id,hd};
		int ori=l-hd,tl=(r-ori)%len[id],rid=(r-ori)/len[id];
		if(rid==0)val[x]=pre[id][tl]-(hd?pre[id][hd-1]:0);
		else val[x]=pre[id][tl]+(rid*sum[id]-(hd?pre[id][hd-1]:0));
	} void push(int l,int r,int x){ // pushdown
		if(laz[x].id){
			int m=l+r>>1;
			int id=laz[x].id,hd=laz[x].hd;
			int mid=(hd+(m-l+1))%len[id];
			mark(l,m,x<<1,id,hd);
			mark(m+1,r,x<<1|1,id,mid);
			laz[x].id=0;
		}
	} void modifyt(int l,int r,int ql,int qr,int x){ // tag
		if(ql<=l&&r<=qr){
			mark(l,r,x,id,(l-lpos)%len[id]);
			return;
		} int m=l+r>>1; push(l,r,x);
		if(ql<=m)modifyt(l,m,ql,qr,x<<1);
		if(m<qr)modifyt(m+1,r,ql,qr,x<<1|1);
		val[x]=val[x<<1]+val[x<<1|1]; 
	} void modifyc(int l,int r,int ql,int qr,int x,bool tg){ // brute force : change
		if(ql>qr)return;
		if(l==r){
			val[x]=f[l];
			if(tg)laz[x]={id,(l-lpos)%len[id]};
			return;
		} int m=l+r>>1; push(l,r,x);
		if(ql<=m)modifyc(l,m,ql,qr,x<<1,tg);
		if(m<qr)modifyc(m+1,r,ql,qr,x<<1|1,tg);
		val[x]=val[x<<1]+val[x<<1|1];
	} ll query(int l,int r,int ql,int qr,int x){
		if(ql>qr)return 0;
		if(ql<=l&&r<=qr)return val[x];
		ll m=l+r>>1,ans=0; push(l,r,x);
		if(ql<=m)ans+=query(l,m,ql,qr,x<<1);
		if(m<qr)ans+=query(m+1,r,ql,qr,x<<1|1);
		return ans;
	} void forms(int l,int r,int ql,int qr,int x){ // form current string [ql,qr]
		if(ql>qr)return;
		if(l==r){
			if(laz[x].id)tmp+=qt[laz[x].id][laz[x].hd];
			else tmp+=ct[l-1];
			return;
		} int m=l+r>>1; push(l,r,x);
		if(ql<=m)forms(l,m,ql,qr,x<<1);
		if(m<qr)forms(m+1,r,ql,qr,x<<1|1);
	}
}st;

int main(){
//	freopen("P5599_5.in","r",stdin);
//	freopen("P5599_5.out","w",stdout);
	// mp
	for(int i='A';i<='Z';i++)mp[i]=i-'A';
	for(int i='a';i<='z';i++)mp[i]=26+(i-'a');
	for(int i='0';i<='9';i++)mp[i]=52+(i-'0');
	
	// read & init
	cin>>lc>>nw>>q>>ct;
	for(int i=1;i<=nw;i++){
		string wrd;
		cin>>wrd,ac.ins(wrd);
	} ac.build(),ac.run(),st.build(1,lc,1);
	
	// solve
	for(int i=1;i<=q;i++){
		int op,l,r,ls; scanf("%d%d%d",&op,&l,&r),ls=r-l+1,st.lpos=l;
		if(op==1){
			ll rpos=min(r,l+L),ans=0,p=0;
			tmp="",st.forms(1,lc,l,rpos,1);
			for(int i=l;i<=rpos;i++)ans+=ac.val[p=ac.son[p][mp[tmp[i-l]]]];
			printf("%lld\n",ans+st.query(1,lc,rpos+1,r,1));
		} else{
			string t; cin>>t,len[++id]=t.size(),pre[id].resize(len[id]);
			int lpos=max(1,l-L+1),rpos=min(lc,r+L-1),p=0;
			if(ls<=L*2+len[id]*2){
				tmp="",st.forms(1,lc,lpos,rpos,1); // get current string
				for(int i=lpos;i<=rpos;i++){
					char it=(i<l||i>r?tmp[i-lpos]:t[(i-l)%len[id]]);
					p=ac.son[p][mp[it]];
					if(i>=l)f[i]=ac.val[p];
				} st.modifyc(1,lc,l,r,1,1),st.modifyc(1,lc,r+1,rpos,1,0);
			} else{
				// front section : [l-L+1,l+L-1]
				int led=l+L-1,rbg=r-L+1;
				while((led-l)%len[id])led++;
				tmp="",st.forms(1,lc,lpos,l-1,1);
				for(int i=lpos;i<led+len[id];i++){
					char it=(i<l?tmp[i-lpos]:t[(i-l)%len[id]]);
					p=ac.son[p][mp[it]];
					if(i>=l){
						if(i<led)f[i]=ac.val[p];
						else pre[id][i-led]=(i>led?pre[id][i-led-1]:0)+ac.val[p];
					}
				} sum[id]=pre[id][len[id]-1];
				st.modifyc(1,lc,l,led-1,1,1),st.modifyt(1,lc,led,r,1);
				
				// back section
				tmp="",st.forms(1,lc,r+1,rpos,1),p=0;
				for(int i=rbg;i<=rpos;i++){
					char it=(i>r?tmp[i-r-1]:t[(i-l)%len[id]]);
					p=ac.son[p][mp[it]];
					if(i>r)f[i]=ac.val[p];
				} st.modifyc(1,lc,r+1,rpos,1,0);
			} qt[id]=t;
		}
	}
	
	return 0;
}

如果您看懂了这篇题解就点个赞吧 qwq。
    • 1

    【XR-4】文本编辑器

    信息

    ID
    4605
    时间
    1000~2000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 44ms