c/c++语言开发共享CodeForces 1313E Concatenation with intersection

洛谷题目页面传送门 & codeforces题目页面传送门

给定(3)个字符串(a,b,c,|a|=|b|=n,|c|=m)，求满足以下全部条件的有序区间对(([l1,r1],[l2,r2]))的个数：

1. ([l1,r1]cap[l2,r2]neqvarnothing)；
2. (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非常难