CF1976D Invertible Bracket Sequences Solution

· · 题解

CF1976D Invertible Bracket Sequences Solution

提供一种不同的做法。

将 ( 看作 1，) 看作 -1。设 s_i 表示前缀和，特殊的，规定 s_0=0。

若 [l,r] 合法当且仅当 s_{l-1}-\max_{l\le i\le r}s_i\ge 0，且 s_{l-1}=s_r。

按 s 的最值分治，设 [L,R] 的最值点为 mid，用 ST 表维护容易。按照套路，枚举较短的一边，另一边数据结构处理。

以枚举 l 为例，首先要满足 s_{l-1}-s_{mid}\ge 0，然后相当于查询 [mid,R] 中有多少个 s_r=s_{l-1}，用主席树容易维护。

枚举 r 同理，注意 s 有负数，在主席树上需要整体位移 n 个单位长度。

时间复杂度 O(n\log n\log V)，可以通过本题。

余望余之神迹，搔首对天长叹，复高吟一绝云：

轮扁斫轮亦有言，应心妙处不可传。 但能付汝皆糟粕，何必孜孜学圣贤！

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
    return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MOD(1e9+7);
template<typename T>
inline T add(T x){return x;}
template<typename T,typename... types>
inline T add(T x,types... y){T z=add<T>(y...);return x+z>=MOD?x+z-MOD:x+z;}
template<typename T>
inline T mul(T x){return x;}
template<typename T,typename... types>
inline T mul(T x,types... y){return (ll)x*mul<T>(y...)%MOD;}
inline int sub(int x,int y){return add(x-y,MOD);}

const int MAXN(2e5+10);

int n;
char t[MAXN];
int s[MAXN];
int T;

struct ST
{
    int st[MAXN][20],lg[MAXN];
    inline int cmp(int x,int y){return s[x]>s[y]?x:y;}
    inline void build()
    {
        lg[0]=-1;
        rep(i,1,n) st[i][0]=i,lg[i]=lg[i>>1]+1;
        rep(j,1,lg[n]) rep(i,1,n-(1<<j)+1) st[i][j]=cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        return;
    } 
    inline int query(int x,int y)
    {
        int k=lg[y-x+1];
        return cmp(st[x][k],st[y-(1<<k)+1][k]);
    }
};
ST st;

int rt[MAXN];

namespace seg
{
    struct T{int ls,rs,sum;};
    T tree[MAXN*60];
    int tot;

    inline void init_()
    {
        rep(i,0,n+1) rt[i]=0;
        rep(i,0,tot) tree[i].ls=0,tree[i].rs=0,tree[i].sum=0;
        tot=0;
        return; 
    }

    inline int lc(int p){return tree[p].ls;}
    inline int rc(int p){return tree[p].rs;}

    inline void update(int&u,int pre,int l,int r,int p)
    {
        u=++tot;
        tree[u]=tree[pre];
        tree[u].sum++;
        if(l==r) return;
        int mid=(l+r)>>1; 
        if(p<=mid) update(tree[u].ls,lc(pre),l,mid,p);
        else update(tree[u].rs,rc(pre),mid+1,r,p);
        return;
    }

    inline int query(int u,int l,int r,int p)
    {
        if(!u) return 0;
        if(l==r) return tree[u].sum;
        int mid=(l+r)>>1;
        if(p<=mid) return query(lc(u),l,mid,p);
        else return query(rc(u),mid+1,r,p);
    }
}

inline int query(int l,int r,int k)
{
    if(l>r) return 0;
    else if(l-1<0) return seg::query(rt[r],0,n<<1,k+n);
    else return seg::query(rt[r],0,n<<1,k+n)-seg::query(rt[l-1],0,n<<1,k+n);
}

inline ll CDQ(int l,int r)
{
    if(l>=r) return 0ll;
    int mid=st.query(l,r);
    ll ans=0;
    if(mid-l<r-mid){rep(i,l,mid) if(2*s[i-1]-s[mid]>=0) ans+=query(mid,r,s[i-1]);} 
    else{rep(i,mid,r) if(2*s[i]-s[mid]>=0) ans+=query(l-1,mid-1,s[i]);} 
    return ans+CDQ(l,mid-1)+CDQ(mid+1,r);
}

inline void solve()
{
    scanf("%s",t+1);
    getchar();
    n=strlen(t+1);
    rep(i,1,n) s[i]=s[i-1]+(t[i]=='('?1:-1);
    st.build();
    seg::init_();
    seg::update(rt[0],rt[n+1],0,n<<1,0);
    rep(i,1,n) seg::update(rt[i],rt[i-1],0,n<<1,s[i]+n);
    printf("%lld\n",CDQ(1,n));
    return;
}

int main()
{
    T=read();
    while(T--) solve();
    return 0;
}