题解：P11305 [COTS 2016] 删除 Brisanje

· · 题解

问题描述

传送门。见原题题目描述。

思路

你说得对，但是只用哈希、二分、线段树可以轻松通过。

分为两种情况：

对于第一种情况，二分一个长度 x，对于所有哈希值相同的子串，记录最后一次出现的左端点，判断其他右端点是否在它的左边，就可以处理不重叠的要求了，用了一个 std::map，时间复杂度 \mathcal{O}(n\log^2n)。

对于第二种情况，类似于 [NOI2016] 优秀的拆分，先考虑形如 AA 的串。不妨设 l_i 为以 i 为右端点最长 AA 串的一半长度，不妨设 r_i 为以 i 为左端点最长 AA 串的一半长度，答案即为：

\max\limits_{i=1}^{n-1}l_i+r_{i+1}

好，现在考虑如何描述所有 AA 串，对于长度为 2i 的 AA 串：

如果我们在字符串上每隔 i 设置一个观察点，那么所有 AA 串必然包含两个观察点。

相邻观察点的 LCP（最长公共前缀） 与 LCS（最长公共后缀） 拼起来的字符串即为经过的两点上的最长 AA 串。若 LCP 与 LCS 的和大于 i，说明它们相交，可以有让一段区间多出长度为 i 的选择。例如 \texttt{ABC(AB)CAB}，其中括号是重叠的部分，那么出现了三个 AA 串：\texttt{ABCABC},\texttt{BCABCA},\texttt{CABCAB}。

可以分析，这样的一段区间不会超过 n\log n 个，如果用哈希求 LCP 和 LCS，时间复杂度是 \mathcal{O}(n\log^2n) 的。

现在只需要对于每个左端点和右端点，当作一个操作，取一个最大值，有 n\log n 次修改，最后统一查询，可以离线下来对于长度 i 排序，从小到大处理，就成了区间赋值，用线段树处理，时间复杂度也是 \mathcal{O}(n\log^2n) 的。

最后将两种答案取最大值，得到最终答案，总时间复杂度 \mathcal{O}(n\log^2n)。

综上，我们在 \mathcal{O}(n\log^2n) 的时间复杂度下解决这道缝合问题。

细节

自然溢出？被卡了。单哈希？也被卡了。所以只能写双模哈希。

注意多个二分的最大边界条件。

代码

AC记录。代码轻微压行、卡常。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10,mod1=1e9+7,mod2=1e9+9,base1=19491001,base2=19370707;
struct SegmentTree{
    struct node{int l,r,w;}t[maxn<<2];
    int ls(int u){return u<<1;}
    int rs(int u){return u<<1|1;}
    void pushdown(int u){
        if(!t[u].w)return;
        t[ls(u)].w=t[u].w;
        t[rs(u)].w=t[u].w;
        t[u].w=0;
    }
    void build(int u,int l,int r){
        t[u]={l,r,0};
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls(u),l,mid);
        build(rs(u),mid+1,r);
    }
    void modify(int u,int l,int r,int w){
        if(r<t[u].l||t[u].r<l)return;
        if(l<=t[u].l&&t[u].r<=r){t[u].w=w;return;}
        pushdown(u);
        modify(ls(u),l,r,w);
        modify(rs(u),l,r,w);
    }
    int query(int u,int x){
        if(x<t[u].l||t[u].r<x)return 0;
        if(x<=t[u].l&&t[u].r<=x)return t[u].w;
        pushdown(u);
        return query(ls(u),x)^query(rs(u),x);
    }
}Tl,Tr;//区间赋值线段树
struct num{
    int h1,h2;num(int a=0,int b=0){h1=a;h2=b;}
    friend bool operator<(const num &a,const num &b){
        if(a.h1!=b.h1)return a.h1<b.h1;
        return a.h2<b.h2;
    }
    friend bool operator ==(const num &a,const num &b){return a.h1==b.h1&&a.h2==b.h2;}
    friend num operator + (const num &a,const num& b){return num((a.h1+b.h1)%mod1,(a.h2+b.h2)%mod2);}
    friend num operator - (const num &a,const num& b){return num((a.h1-b.h1+mod1)%mod1,(a.h2-b.h2+mod2)%mod2);}
    friend num operator * (const num &a,const num& b){return num((a.h1*b.h1)%mod1,(a.h2*b.h2)%mod2);}
}h[maxn],p[maxn],base(base1,base2);//双哈希结构体
int n;
num get(int l,int r){return h[r]-h[l-1]*p[r-l+1];}
int lcp(int x,int y){
    int l=0,r=x,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(get(x-mid+1,x)==get(y-mid+1,y))l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}//哈希求LCP
int lcs(int x,int y){
    int l=0,r=n-y+1,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(get(x,x+mid-1)==get(y,y+mid-1))l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}//哈希求LCS
struct node{int l,r,w;};vector<node>Vr,Vl;
bool cmp(const node& a,const node& b){
    if(a.w!=b.w)return a.w<b.w;
    if(a.l!=b.l)return a.l<b.l;
    return a.r<b.r;
}//排序线段
map<num,int>st;
bool check(int mid){
    st.clear();
    for(int i=n-mid+1;i>=1;i--){
        const num&& h=get(i,i+mid-1);
        if(!st.count(h))st[h]=i;
        else if(st[h]>=i+mid)return 1;
    }
    return 0;
}//第一种情况
signed main(){
    // freopen("str.in","r",stdin);
    // freopen("str.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;cin>>s;s=' '+s;
    n=s.size()-1;p[0]={1,1};
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*base+num{s[i],s[i]};
        p[i]=p[i-1]*base;
    }//哈希初始化
    Vl.clear();Vr.clear();
    for(int i=1;i<=n;i++){
        for(int j=i,k=i+i;k<=n;j+=i,k+=i){
            int l=max(k-lcp(j,k)+i,k),r=min(k+lcs(j,k)-1,k+i-1);
            if(l>r)continue;
            Vl.push_back({l,r,i});
            Vr.push_back({l-i*2+1,r-i*2+1,i});
        }
    }//求线段
    sort(Vl.begin(),Vl.end(),cmp);
    sort(Vr.begin(),Vr.end(),cmp);
    Tl.build(1,1,n);Tr.build(1,1,n);
    for(auto [l,r,w]:Vl)Tl.modify(1,l,r,w);
    for(auto [l,r,w]:Vr)Tr.modify(1,l,r,w);//离线赋值
    int l=0,r=n/2,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }//第一种情况
    for(int i=1;i<n;i++)
        ans=max(ans,Tl.query(1,i)+Tr.query(1,i+1));//第二种情况
    cout<<ans;
    return 0;
}