专栏文章

题解：CF1313E Concatenation with intersection

sshiruoyu114514
CF1313E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mineopt6
此快照首次捕获于
2025/12/02 01:11
3 个月前
此快照最后确认于
2025/12/02 01:11
3 个月前
查看原文
给定两个长度为 nn 的字符串 a,ba,b 以及一个长度为 mm 的字符串 ss。问有多少个四元组 (l1,r1,l2,r2)(l_1,r_1,l_2,r_2) 满足 a[l1:r1]+b[l2:r2]=sa[l_1:r_1]+b[l_2:r_2]=s。n≤5×105,m≤106n \le 5 \times 10^5,m \le 10^6。
一个比较错误的切入点是枚举 aa 贡献的前缀。如果你想要使用后缀数组的话，可以处理出来 ss 对应前缀所能匹配的后缀数组区间以及 ss 后缀的反串在 bb 反串所能匹配的后缀数组区间，然后就转化为了以下问题：
有 nn 组询问，每组询问形如：给定 [l1,r1][l2,r2][l_1,r_1][l_2,r_2]，求 ∑i=l1r1∑j=l2r2[∣ai−bj∣<m]\sum \limits_{i=l_1}^{r_1} \sum \limits_{j=l_2}^{r_2} [|a_i-b_j| < m]。
显然做不了！
事实上，我们需要注意到的一件事情是，[l1,r1][l2,r2][l_1,r_1][l_2,r_2] 的区间长度总和为 mm。也就是说，我们只需要保证 r2<l1+m−1r_2<l_1+m-1 并且 r2≥l1r_2 \ge l_1 即可。
现在我们考虑怎么刻画 r1r_1 与 l2l_2 的计数。
发现在不考虑总长度和为 mm 的情况下，r1r_1 与 l2l_2 都呈一个区间。
考虑预处理 AiA_i 为 a[i:n]a[i:n] 与 ss 的 LCP，BiB_i 为 b[1:i]b[1:i] 与 ss 的 LCS。
我们就能够发现，合法的方案数就恰好为 max⁡(0,(Al1−(Al1≥m))+(Br1−(Br1≥m))−(m−1))\max(0,(A_{l_1}-(A_{l_1} \ge m))+(B_{r_1}-(B_{r_1} \ge m))-(m-1))。有这么一个特判是因为 aa 与 bb 的贡献不能为空。
令 vai=Ai−(Ai≥m),vbiva_i=A_i-(A_i \ge m),vb_i 同理，则所求为：
∑r≥l,r<l+m−1max⁡(0,va+vb−m+1)\sum \limits_{r \ge l,r < l+m-1} \max(0,va+vb-m+1)
使用你喜欢的数据结构处理即可。时间复杂度 O(nlog⁡n)O(n \log n)。
CPP
#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int maxn=1e6;
constexpr int base=31;
constexpr int mod=998244353;

int powbase[maxn+5];

struct String{
	string s;
	vector<int> hsh;
	int n;
	
	void init(){
		cin>>s;
		n=s.length();
		s=" "+s;
		hsh.resize(n+1,0);
		for(int i=1;i<=n;i++){
			hsh[i]=(hsh[i-1]*base+s[i])%mod;
			//cout<<hsh[i]<<" ";
		}
		//cout<<"\n";
	}
	
	int calc(int l,int r){
	//	cout<<"Calc "<<l<<" "<<r<<"\n";
		return (hsh[r]-hsh[l-1]*powbase[r-l+1]%mod+mod)%mod;
	}
	
	char& operator [](int x){
		//cerr<<"Call "<<x<<"\n";
		return s[x];
	}
};

int n,m;
String a,b,s;

int longa[maxn+5],longb[maxn+5];

struct bit{
	int v[maxn+5];
	
	void update(int pos,int value){
		pos++;
		while(pos){
			v[pos]+=value;
			pos-=pos&(-pos);
		}
	}
	
	int quary(int pos){
		pos++;
		int ans=0;
		while(pos<=m+1){
			ans+=v[pos];
			pos+=pos&(-pos);
		}
		return ans;
	}
}ct,v;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	powbase[0]=1;
	for(int i=1;i<=maxn;i++){
		powbase[i]=powbase[i-1]*base%mod;
	}
	cin>>n>>m;
	a.init();
	b.init();
	s.init();
	for(int i=1;i<=n;i++){
		if(a[i]!=s[1]){
			longa[i]=0;
		}
		else{
			int l=1,r=min(n-i+1,m);
			while(l<r){
				int mid=((l+r)>>1)+1;
				if(a.calc(i,i+mid-1)==s.calc(1,mid)){
					l=mid;
				}
				else{
					r=mid-1;
				}
			}
			longa[i]=l;
		}
	}
	for(int i=1;i<=n;i++){
		if(b[i]!=s[m]){
			longb[i]=0;
		}
		else{
			int l=1,r=min(i,m);
			while(l<r){
				int mid=((l+r)>>1)+1;
				if(b.calc(i-mid+1,i)==s.calc(m-mid+1,m)){
					l=mid;
				}
				else{
					r=mid-1;
				}
			}
			longb[i]=l;
		}
	}
	int ans=0;
//	for(int l=1;l<=n;l++){
//		for(int r=1;r<=n;r++){
//			if(r>=l&&r<l+m-1){
//				int va=longa[l]-(longa[l]>=m);
//				int vb=longb[r]-(longb[r]>=m);
//				if(vb>=max(0ll,m-1-va)){
//					ans+=va+vb-m+1;
//				}
//			}
//		}
//	}
	vector<pair<int,int>> quary[n+5];
	for(int l=n;l>=1;l--){
		int va=m-1-(longa[l]-(longa[l]>=m));//注意此处 va 为题解中的 m-1-va
		quary[l].push_back(make_pair(va,1));
		if(l+m-1<=n){
			quary[l+m-1].push_back(make_pair(va,-1));
		}
	}
	for(int l=n;l>=1;l--){
		int vb=longb[l]-(longb[l]>=m);
		ct.update(vb,1);
		v.update(vb,vb);
		for(auto j:quary[l]){
			ans+=(-ct.quary(j.first)*(j.first)+v.quary(j.first))*j.second;
		}
	}
	cout<<ans;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...