题解：P9266 [PA 2022] Nawiasowe podziały

· · 题解

一个子串的括号配对了，它配对的对象肯定只会有一个，可以预处理出来。

看到强制 k 段这个条件，我们肯定就会觉得这满足凸性和四边形不等式，就觉得这可以 wqs 二分。

事实上，这确实是满足的，可我不会证明。

那先 wqs 二分把这个 k 的限制消去，但我们发现用一般的四边形不等式优化 dp，我们无法快速计算 w(j+1,i) 的贡献，但是我们发现我们可以使用类似莫队移动指针的方式计算。

此时我们就可以用简化 LARSCH 算法求解。

具体步骤如下：

设现在在处理 (l,r]，mid 为此区间的中点 \lfloor \frac{l+r+1}{2}\rfloor。

  1. 遍历 [opt_l,opt_{r,l}]，以这些为决策点更新 mid。

  2. 递归求解 (l,mid]。

  3. 遍历 (l,mid]，以这些为决策点更新 r。

  4. 递归求解 (mid,r]。

inline void LARSCH(int l,int r){//处理 (l,r] 
    int mid=(l+r+1)/2;
    for(int j=opt[l];j<=opt[r];j++) if(w(j,mid)>dp[mid]) dp[mid]=w(j,mid);
    if(mid<r) LARSCH(l,mid);//注意是否进行递归的判断
    for(int j=l+1;j<=mid;j++) if(w(j,r)>dp[r]) dp[r]=w(j,r);
    if(l<mid) LARSCH(mid,r);//注意是否进行递归的判断
}

你会发现，此算法解决从 opt_l 到 opt_r 的这段可以移动指针，从 l+1 到 mid 也可以移动指针。

可以证明这种简化 LARSCH 算法时间复杂度依旧是 O(n\log n)，可以看 OI-wiki。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int n,m,dp[500010],opt[500010],col[500010];
int st[500010],top,pos[500010],id;
struct node{
    int L,R,ans,cnt[500010];
    inline node(){L=1,R=0,ans=0;}
    inline void add(int x,bool p,int y){
        if(p) if(s[x]==')' && pos[x]>=y) ans+=++cnt[col[x]];else;
        else if(s[x]=='(' && pos[x]<=y) ans+=++cnt[col[x]];
    } 
    inline void del(int x,bool p,int y){
        if(p) if(s[x]==')' && pos[x]>=y) ans-=cnt[col[x]]--;else;
        else if(s[x]=='(' && pos[x]<=y) ans-=cnt[col[x]]--;
    }
    inline int w(int j,int i){
        if(j>i) return 0;
        while(L>j) add(--L,0,R);
        while(R<i) add(++R,1,L);
        while(L<j) del(L++,0,R);
        while(R>i) del(R--,1,L);
        return ans;
    }
}A,B;
inline void LARSCH(int l,int r,int T){//处理 (l,r] 
    int mid=(l+r+1)/2;
    for(int j=opt[l];j<=opt[r];j++) if(dp[j-1]+A.w(j,mid)+T<dp[mid]) dp[mid]=dp[j-1]+A.w(j,mid)+T,opt[mid]=j;
    if(mid<r) LARSCH(l,mid,T);//注意是否进行递归的判断
    for(int j=l+1;j<=mid;j++) if(dp[j-1]+B.w(j,r)+T<dp[r]) dp[r]=dp[j-1]+B.w(j,r)+T,opt[r]=j;
    if(l<mid) LARSCH(mid,r,T);//注意是否进行递归的判断
}
inline int f(int x){
    for(int i=1;i<=n;i++) dp[i]=dp[0]+A.w(1,i)+x,opt[i]=1; 
    LARSCH(1,n,x);
    int T=n,cnt=0;
    while(T) cnt++,T=opt[T]-1;
    return cnt;
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>n>>m>>s,s=" "+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='('){
            st[++top]=i,pos[i]=n+1;
            continue;
        }
        if(!top) continue;
        int j=st[top--];
        pos[i]=j,pos[j]=i,col[i]=col[j]=(col[j-1] ? col[j-1] : ++id);
    }
    int l=0,r=1e10,ans=0,mid=0;
    while(l<=r)
        if(f(mid=l+r>>1)<=m) ans=mid,r=mid-1;
        else l=mid+1;
    f(ans);
    cout<<dp[n]-ans*m;
    return 0;
}

给个移动指针 LARSCH 的通用模板。

struct node{
    int L,R,ans;
    inline node(){L=1,R=0,ans=0;}
    inline void add(int x,bool p,int y){

    } 
    inline void del(int x,bool p,int y){

    }
    inline int w(int j,int i){
        if(j>i) return 0;
        while(L>j) add(--L,0,R);
        while(R<i) add(++R,1,L);
        while(L<j) del(L++,0,R);
        while(R>i) del(R--,1,L);
        return ans;
    }
}A,B;
inline void LARSCH(int l,int r,int T){//处理 (l,r] 
    int mid=(l+r+1)/2;
    for(int j=opt[l];j<=opt[r];j++) if(dp[j-1]+A.w(j,mid)+T<dp[mid]) dp[mid]=dp[j-1]+A.w(j,mid)+T,opt[mid]=j;
    if(mid<r) LARSCH(l,mid,T);//注意是否进行递归的判断
    for(int j=l+1;j<=mid;j++) if(dp[j-1]+B.w(j,r)+T<dp[r]) dp[r]=dp[j-1]+B.w(j,r)+T,opt[r]=j;
    if(l<mid) LARSCH(mid,r,T);//注意是否进行递归的判断
}