CodeForces 1313E Concatenation with intersection

Z算法+值域BIT

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

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

1. \([l1,r1]\cap[l2,r2]\neq\varnothing\)；
2. \(a_{l1\sim r1}+b_{l2\sim r2}=c\)。

\(n\in\left[1,5\times10^5\right],m\in[2,2n]\)。

\(c\)由\(a,b\)各一个子串拼接而成，不难想到两面夹击——从\(a_{l1}\)往后与\(c\)的前缀匹配、从\(b_{r2}\)往前与\(c\)的后缀匹配。于是我们可以预处理出\(2\)个数组\(lcP:lcP_i=\max\limits_{a_{i\sim i+j-1}=c_{1\sim j}}\{j\},Lcs:Lcs_i=\max\limits_{b_{i-j+1\sim i}=c_{m-j+1\sim m}}\{j\}\)，对\(c+\texttt!+a,\mathrm{rev}(c)+\texttt!+\mathrm{rev}(b)\)这\(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)]\neq\varnothing\)，即\(\max(l1,r2-m+x+1)\leq\min(l1+x-1,r2)\)，即\(\begin{cases}l1\leq l1+x-1\\l1\leq r2\\r2-m+x+1\leq l1+x-1\\r2-m+x+1\leq r2\end{cases}\)，即\(\begin{cases}x\in[1,m-1]\\r2\in[l1,l1+m-2]\end{cases}\)。

再考虑满足条件\(2\)的充要条件。满足条件\(2\)当且仅当\(\begin{cases}x\leq lcP_{l1}\\m-x\leq Lcs_{r2}\end{cases}\)，即\(x\in[m-Lcs_{r2},lcP_{l1}]\)。

综上，若已知\(l1,r2,x\)，那么满足题目中的所有条件当且仅当\(\begin{cases}r2\in[l1,l1+m-2]\\x\in[\max(1,m-Lcs_{r2}),\min(m-1,lcP_{l1})]\end{cases}\)。显然\(\forall l1\in[1,n],\forall r2\in[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})+1\geq1\)和\(\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\)。

所以答案显然为\(\sum\limits_{l1=1}^n\sum\limits_{r2\in[l1,\min(n,l1+m-2)],\max(1,m-Lcs_{r2})\leq\min(m-1,lcP_{l1})}(\min(m-1,lcP_{l1})-\max(1,m-Lcs_{r2})+1)\)。由于当\(l1\)单调递增时，\(r2\)所在区间的左端点和右端点也同时单调递增，不妨在值域上建一个BIT，然后从左往右枚举\(l1\)，每次添加、删除各\(0\sim1\)个\(\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\)，则对答案的贡献是\(cnt\cdot(\min(m-1,lcP_{l1})+1)+sum\)。哦对了，别忘了在\(l1=1\)的时候把\(\forall r2\in[1,\min(n,m-1)],\max(1,m-Lcs_{r2})\)全部添加到BIT里哦！

\(\forall r2\in[1,n]\)，\(\max(1,m-Lcs_{r2})\)最多会被添加、删除各\(1\)次，每次\(\mathrm O(\log_2m)\)，所以复杂度\(\mathrm O(n\log_2m)\)。再加上之前\(\mathrm O(n+m)\)的Z算法，总复杂度\(\mathrm O(m+n\log_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+1];//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 %lld\n",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非常难

原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-1313E.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有