题解：CF1976D Invertible Bracket Sequences

· · 题解

题意

给定合法括号匹配序列，求区间取反后仍然为合法序列的连续区间个数。

Sol

如果画出折线图，本题就很好思考。

转化成 +1,-1 的序列，求前缀和，应当满足任意时刻 sum_i>0，考虑画出折线图，如图所示.

每次取反首先要满足左括号数量等于右括号数量，所以选择的两个端点 l,r 必须满足 sum_l=sum_r ，对应图上就是 y 坐标相等。

由于任意时刻 sum_i>0，所以对于区间 [l,r]，最大值设为 sum_{x}，应当满足 sum_x-sum_l \le sum_l-0，对应图上，就是最高点翻转后仍然在 x 轴上方。

考虑对于确定的 y=sum_i，求出多少个区间可以翻着，由于区间最大值可合并性，若 sum_l=sum_{mid}=sum_r=y，满足 [l,mid] 可翻折，[mid,r] 可翻折，则 [l,r] 可翻折。(可以考虑图上的 H,L,M 三点)。

也就是说，钦定右端点 r，找到最小的左端点 l，满足 \max\limits_{i=l}^r sum[i]\le2sum[l]，区间最大值可以用线段树或 st 表轻松维护，再记录一下上一个不满足条件位置即可。

对于确定的 y 已经知道如何求了，可以考虑扫描线从低到高扫描一遍累加答案。

时间复杂度 O(n\log n)。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 200005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
ll n,a[N];
string s;
ll sum[N];
struct sgt{
    #define mid ((l+r)>>1)
    #define ls (p<<1)
    #define rs (p<<1|1)
    ll mx[N*4],lzy[N*4];
    void lt(ll p,ll x){
        mx[p]+=x;
        lzy[p]+=x;
    }
    void build(ll p,ll l,ll r){
        mx[p]=lzy[p]=0;
        if(l==r){
            mx[p]=sum[l];
            return ;
        }
        build(ls,l,mid);
        build(rs,mid+1,r);
        mx[p]=max(mx[ls],mx[rs]);
    }
    void pushdown(ll p){
        lt(ls,lzy[p]);
        lt(rs,lzy[p]);
        lzy[p]=0;
    }
    void upd(ll p,ll l,ll r,ll le,ll ri,ll t){
        if(le<=l&&ri>=r){
            lt(p,t);
            return ;
        }
        pushdown(p);
        if(le<=mid)upd(ls,l,mid,le,ri,t);
        if(ri>mid)upd(rs,mid+1,r,le,ri,t);
        mx[p]=max(mx[ls],mx[rs]);
    }
    ll qr(ll p,ll l,ll r,ll le,ll ri){
        if(le<=l&&ri>=r)return mx[p];
        pushdown(p);
        ll ans=-inf;
        if(le<=mid)ans=max(ans,qr(ls,l,mid,le,ri));
        if(ri>mid)ans=max(ans,qr(rs,mid+1,r,le,ri));
        return ans;
    }
}T;
vector<ll>v[N];
void sol(){
    cin>>s;
    n=s.size();
    s=" "+s;
    for(int i=0;i*2<=n;i++)v[i].clear();
    for(int i=1;i<=n;i++){
        if(s[i]=='(')a[i]=1;
        else a[i]=-1;
        sum[i]=sum[i-1]+a[i];
        v[sum[i]].push_back(i);
    }
    ll res=0;
    T.build(1,1,n);
    for(int i=0;i*2<=n;i++){
        ll last=-1;
        for(int j=0;j+1<v[i].size();j++){
            auto t=T.qr(1,1,n,v[i][j],v[i][j+1]);
            if(t>i*2)last=j;
            res+=j-last;
        }
    }
    cout<<res<<endl;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll ttt;
    cin>>ttt;
    while(ttt--)sol();
    return 0;
}