CF1750E

dottle · 2022-11-07 01:25:07 · 题解

先来考虑一个子串怎么算最小贡献，设其有 L 个左括号，R 个右括号，X 对已经匹配的括号。

首先，存在一个构造，操作次数为 \max(L,R)-X，不妨设 L\ge R，反之亦然：

• 依次考虑每一个左括号，如果有未匹配的右括号，则这些右括号在此左括号前面。可以直接把左括号转到某一个右括号前面。否则在该左括号右边加一个右括号。

并且，我们发现每次操作只会减少至多一个未匹配的左括号或者右括号，因此上述构造取到最优。

现在，我们来分别求出 \sum\max(L,R) 和 \sum X。

对于 \sum X，考虑原串中每一对匹配的括号的贡献。如在子串中其中某个括号匹配了，则一定是与对方匹配。这样，这对匹配将在 l\times (n-r+1) 个子串中出现。

对于 \max(L,R)，考虑其等于 [(R+L)+|L-R|]/2，前一个小括号里的好求。求绝对值那一项的和，将左括号视为 1，右括号视为 -1，该值等于区间和的绝对值。那么我们将所有前缀和从小到大排序为 s，那么绝对值之和就是 \sum_{i=1}^n\sum_{j=i}^ns_j-s_i，此式计算不难。

时间复杂度为 O(n)（若将排序视为对 1\sim n 的计数排序），也很好写。

代码中标记了哪个式子是在算哪一部分。

#include<bits/stdc++.h>
#define int long long
const int N=1000005;
using namespace std;

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    vector<int> a(1);
    int sum=0;
    for(int i=0;i<n;i++){
        if(s[i]=='(')sum++;
        else sum--;
        a.push_back(sum);
    }
    sort(a.begin(),a.end());
    int res=0,ns=0;
    for(int i=0;i<=n;i++){
        res+=i*a[i]-ns;//|L-R|
        res+=i*(n-i+1);// L+R
        ns+=a[i];
    }
    res/=2; 
    stack<int> sss;
    for(int i=0;i<n;i++){
        if(s[i]=='('){
            sss.push(i);
        }else{
            if(sss.empty())continue;
            res-=(sss.top()+1)*(n-i);// X
            sss.pop(); 
        }
    }
    cout<<res<<endl;
}

main(){
    ios::sync_with_stdio(0);
    int _T=1;cin>>_T;
    while(_T--)solve();
}