洛谷题目页面传送门 & codeforces题目页面传送门
给定(3)个字符串(a,b,c,|a|=|b|=n,|c|=m),求满足以下全部条件的有序区间对(([l1,r1],[l2,r2]))的个数:
- ([l1,r1]cap[l2,r2]neqvarnothing);
- (a_{l1sim r1}+b_{l2sim r2}=c)。
(ninleft[1,5times10^5right],min[2,2n])。
(c)由(a,b)各一个子串拼接而成,不难想到两面夹击——从(a_{l1})往后与(c)的前缀匹配、从(b_{r2})往前与(c)的后缀匹配。于是我们可以预处理出(2)个数组(lcp:lcp_i=maxlimits_{a_{isim i+j-1}=c_{1sim j}}{j},lcs:lcs_i=maxlimits_{b_{i-j+1sim i}=c_{m-j+1sim m}}{j}),对(c+texttt!+a,c^mathrm r+texttt!+b^mathrm r)这(2)个字符串各跑一遍z算法即可。
假设我们已经固定住了(l1,r2)。设从(l1)往后延伸了(x)位,从(r2)往前自然就延伸了(m-x)位,于是(r1=l1+x-1,l2=r2-m+x+1)。
考虑满足题目中的条件(1)的充要条件。满足条件(1)当且仅当([l1,r1]cap[l2,r2]=[l1,l1+x-1]cap[r2-m+x+1,r2]=[max(l1,r2-m+x+1),min(l1+x-1,r2)]neqvarnothing),即(max(l1,r2-m+x+1)leqmin(l1+x-1,r2)),即(begin{cases}l1leq l1+x-1\l1leq r2\r2-m+x+1leq l1+x-1\r2-m+x+1leq r2end{cases}),即(begin{cases}xin[1,m-1]\r2in[l1,l1+m-2]end{cases})。
再考虑满足条件(2)的充要条件。满足条件(2)当且仅当(begin{cases}xleq lcp_{l1}\m-xleq lcs_{r2}end{cases}),即(xin[m-lcs_{r2},lcp_{l1}])。
综上,若已知(l1,r2,x),那么满足题目中的所有条件当且仅当(begin{cases}r2in[l1,l1+m-2]\xin[max(1,m-lcs_{r2}),min(m-1,lcp_{l1})]end{cases})。显然(forall l1in[1,n],forall r2in[l1,min(n,l1+m-2)]),(r2)对答案贡献为(max(1,min(m-1,lcp_{l1})-max(1,m-lcs_{r2})+1))。这里面有个(max),比较讨厌,我们把它分成(min(m-1,lcp_{l1})-max(1,m-lcs_{r2})+1geq1)和(min(m-1,lcp_{l1})-max(1,m-lcs_{r2})+1<1)这(2)种情况。对于后者,显然贡献为(0),无需考虑;对于前者,即(max(1,m-lcs_{r2})leq min(m-1,lcp_{l1})),贡献为(min(m-1,lcp_{l1})-max(1,m-lcs_{r2})+1)。
所以答案显然为(sumlimits_{l1=1}^nsumlimits_{r2in[l1,min(n,l1+m-2)],max(1,m-lcs_{r2})leqmin(m-1,lcp_{l1})}(min(m-1,lcp_{l1})-max(1,m-lcs_{r2})+1))。由于当(l1)单调递增时,(r2)所在区间的左端点和右端点也同时单调递增,我们可以用two-pointers维护。不妨在值域上建一个bit,然后从左往右枚举(l1),每次添加、删除各(0sim1)个(max(1,m-lcs_{r2}))。答案中的求和式可以分成分别关于(l1,r2)的(2)部分(min(m-1,lcp_{l1})+1,-max(1,m-lcs_{r2})),对(2)部分分别求和,显然bit不仅要实现值域上的区间求和,还要实现值域上的区间计数。枚举到每个(l1),设添加、删除完(max(1,m-lcs_{r2}))后,值域上的区间([1,min(m-1,lcp_{l1})])内求和的结果为(sum),计数的结果为(cnt),则对答案的贡献是(cntcdot(min(m-1,lcp_{l1})+1)+sum)。哦对了,别忘了在(l1=1)的时候把(forall r2in[1,min(n,m-1)],max(1,m-lcs_{r2}))全部添加到bit里哦!
(forall r2in[1,n]),(max(1,m-lcs_{r2}))最多会被添加、删除各(1)次,每次(mathrm o(log_2m)),所以复杂度(mathrm o(nlog_2m))。再加上之前(mathrm o(n+m))的z算法,总复杂度(mathrm o(m+nlog_2m))。
上代码!
#include<bits/stdc++.h> using namespace std; #define int long long//答案会爆int int lowbit(int x){return x&-x;} const int n=500000,m=1000000; int n/*|a|=|b|*/,m/*|c|*/; char a[n+5],b[n+5],c[m+5];//3个字符串 int lcp[n+1],lcs[n+1];//lcp[i],lcs[i]各表示从a,b的第i位开始向后、向前最多能与c的前缀、后缀匹配的位数 int s;//|d| char d[n+m+5];//临时字符串 void con(char x[],char y[]){//令d=x+'!'+y s=0; for(int i=1;i<=m;i++)d[++s]=x[i]; d[++s]='!'; for(int i=1;i<=n;i++)d[++s]=y[i]; } int z[n+m+2];//z数组 void z_init(){//z算法 z[1]=s; int zl=0,zr=0; for(int i=2;i<=s;i++) if(zr<i){ z[i]=0; while(i+z[i]<=s&&d[i+z[i]]==d[1+z[i]])z[i]++; if(z[i])zl=i,zr=i+z[i]-1; } else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1]; else{ z[i]=zr-i+1; while(i+z[i]<=s&&d[i+z[i]]==d[1+z[i]])z[i]++; zl=i;zr=i+z[i]-1; } } struct bitree{//bit int sum[m+1]/*和*/,cnt[m+1]/*计数*/; void init(){ memset(sum,0,sizeof(sum)); memset(cnt,0,sizeof(cnt)); } void add(int v){//添加 int x=v; while(x<=n)sum[x]-=v,cnt[x]++,x+=lowbit(x); } void del(int v){//删除 int x=v; while(x<=n)sum[x]+=v,cnt[x]--,x+=lowbit(x); } int sum(int x){//求前缀和 int res=0; while(x)res+=sum[x],x-=lowbit(x); return res; } int cnt(int x){//求前缀计数 int res=0; while(x)res+=cnt[x],x-=lowbit(x); return res; } }bit; signed main(){ scanf("%lld%lld%s%s%s",&n,&m,a+1,b+1,c+1); con(c,a); z_init(); for(int i=1;i<=n;i++)lcp[i]=z[m+1+i];//求lcp reverse(b+1,b+n+1);reverse(c+1,c+m+1);con(c,b); z_init(); for(int i=1;i<=n;i++)lcs[i]=z[m+1+(n-i+1)];//求lcs // for(int i=1;i<=n;i++)printf("%lld %lldn",lcp[i],lcs[i]); int ans=0; bit.init(); for(int i=1;i<=min(n,m-1);i++)bit.add(max(1ll,m-lcs[i]));//在l1=1时预先添加r2 in [1,min(n,m-1)] for(int i=1;i<=n;i++){ if(i>1)bit.del(max(1ll,m-lcs[i-1]))/*删除r2=i-1*/,i+m-2<=n&&(bit.add(max(1ll,m-lcs[i+m-2])),0)/*添加r2=i+m-2*/; ans+=(min(m-1,lcp[i])+1)*bit.cnt(min(m-1,lcp[i]))+bit.sum(min(m-1,lcp[i]));//贡献答案 // cout<<ans<<"n"; } cout<<ans; return 0; }
最后说句闲话,你们知道为什么这题难度这么高吗?
因为这场比赛的d非常难
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/600353.html