题解：P12550 [UOI 2025] Reversal ABC

· · 题解

提供一个不需要暴力优化 dp 的做法。

手玩一下这个交换容易发现，当我们交换一对之后，这两个数会彼此锁定。比如 \texttt{AB} 交换之后，左边的 \texttt{B} 不可能凑出 \texttt{BC}，右边的 \texttt{A} 不可能凑出 \texttt{CA}，于是它们就锁死了。

进一步地，我们发现左边的 \texttt{B} 仍然可以移动，但是不能突破左边的第一个 \texttt{C}，右边的 \texttt{A} 也同理。扩展这个性质到操作上，实际上我们是可以选中一串只含两种字母的子串然后在里面邻项交换，直到某种靠后的字母全部在另一种前面就倒闭了。

根据冒泡排序结论，这个交换次数是固定的，我们只能交换“逆序对”（\texttt{AB},\texttt{BC},\texttt{CA} 子序列）数量次。

由于我们每次会把一个子串交换到锁死状态，所以子串的结构之间没有影响。所以我们实际上是对这个串进行划分，使得所有段的“逆序对”数量和最大。直接 dp 就是 \mathcal O(n^2) 的。

考虑优化。我们先证明几个结论：

Lemma 1. 不存在一种优的划分，划分两边的字符相同。
Proof. 考虑这个切点所在的极长连续段，现在我们把它分成了左半边和右半边，在两个段分别贡献“逆序对”。而总有一边贡献得多一点，我们把切点往少的那边挪，让多的那边字符多一些总是不劣的，所以我们一定可以把切点移到连续段的端点处。

Lemma 2. 不存在一种优的划分，有相邻两个段当中出现的字符集合相同。
Proof. 显然，把这两个段合并在一起一定会让“逆序对”数量增多。

据此我们考虑转移 f_i 的时候有哪些决策点是有用的。我们考虑二分（双指针也可以）找出最远的一个 j 满足 (j,i] 只有两种字符，那么根据上述结论，决策点一定在 j+1 所在连续段的端点上（在内部不满足 Lemma 1，再往后移不满足 Lemma 2）。

于是我们把这两个点拿出来转移就可以了。使用两个前缀和计算转移时产生的逆序对即可。

用双指针写即可做到 \mathcal O(n)，\Sigma 几乎是常数所以省去了。效率甩斜率优化几条街。

int tc;
int n;
char c[N];
ll dp[N];
int sum[N][3];
ll psum[N][3];
int ed[N],cut[N];
bool check(int l,int r){
    return !((sum[r][2]-sum[l-1][2])&&(sum[r][1]-sum[l-1][1])&&(sum[r][0]-sum[l-1][0]));
}
ll inv(int l,int r,int op1,int op2){//op1>op2
    return psum[l][op1]-psum[r+1][op1]-1ll*(sum[r][op1]-sum[l-1][op1])*(sum[n][op2]-sum[r][op2]);
}
ll cinv(int l,int r){
    if(sum[r][2]-sum[l-1][2]&&sum[r][1]-sum[l-1][1]){
        return inv(l,r,1,2);
    }
    else if(sum[r][2]-sum[l-1][2]&&sum[r][0]-sum[l-1][0]){
        return inv(l,r,2,0);
    }
    else if(sum[r][1]-sum[l-1][1]&&sum[r][0]-sum[l-1][0]){
        return inv(l,r,0,1);
    }
    return 0;
}
void solve(){
    cin>>n;
    fr1(i,1,n){
        cin>>c[i];
        fr1(j,0,2) sum[i][j]=sum[i-1][j];
        sum[i][c[i]-'A']++;
    }
    psum[n+1][0]=psum[n+1][1]=psum[n+1][2]=0;
    fr2(i,n,1){
        fr1(j,0,2) psum[i][j]=psum[i+1][j];
        psum[i][c[i]-'A']+=sum[n][(c[i]-'A'+1)%3]-sum[i][(c[i]-'A'+1)%3];
    }
    int lst=n;
    ed[n]=n;
    fr2(i,n-1,1){
        if(c[i]!=c[i+1]) lst=i;
        ed[i]=lst;
    }
    fr1(i,1,n) dp[i]=-1e18;
    int r=0;
    fr1(l,1,n){
        while(!check(r+1,l)) r++;
        cut[l]=r;
    }
    fr1(i,1,n){
        int tf=cut[i];
        dp[i]=max(dp[tf]+cinv(tf+1,i),dp[i]);
        dp[i]=max(dp[ed[tf+1]]+cinv(ed[tf+1]+1,i),dp[i]);
    }
    cout<<dp[n]<<'\n';
}
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>tc;
    while(tc--) solve();
    ET;
}
//ALL FOR Zhang Junhao.