解法 #

首先，我们需要知道几点正确匹配的括号序列的性质：

如果我们把左括号换成 1，把右括号换成 -1 的话：

序列的和为 0
任意前缀和不小于 0
前缀和中最大值就是嵌套最多的括号数

根据这些性质，我们需要一个可以支持区间修改和查询最值的数据结构，很明显，就是线段树了。

注意：整个序列的和可以通过查询最后一个元素的值来得到，query 函数就是为了干这个的。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define tr t[root]
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
const int N=1e6;
int n;
struct segt{
    int l,r;
    ll min,max,tag;
}t[N<<2];
void build(int root,int l,int r){
    t[root].l=l;
    t[root].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
}
void addtag(int p,int x){
    t[p].max+=x;
    t[p].min+=x;
    t[p].tag+=x;
}
void spread(int p){
    if(t[p].tag){
        addtag(p<<1|1,t[p].tag);
        addtag(p<<1,t[p].tag);
        t[p].tag=0;
    }
}
void update(int root,int l,int r,int x){
    if(l<=t[root].l&&r>=t[root].r){
        addtag(root,x);
        return;
    }
    spread(root);
    int mid=(t[root].l+t[root].r)>>1;
    if(l<=mid) update(root<<1,l,r,x);
    if(r>mid) update(root<<1|1,l,r,x);
    tr.max=max(t[root<<1].max,t[root<<1|1].max);
    tr.min=min(t[root<<1].min,t[root<<1|1].min);
}
int query(int root,int x){
    if(tr.l==tr.r) return tr.max;
    spread(root);
    int mid=(tr.l+tr.r)>>1;
    if(mid>=x) return query(root<<1,x);
    else return query(root<<1|1,x);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int pos=1;
    vector<int> a(n+1);
    build(1,1,n);
    for1(i,n){
        char ch;
        cin>>ch;
       int val=0;
       if(ch=='L'){
           pos=max(1,pos-1);
           goto write;
       }else if(ch=='R'){
           pos++;
           goto write;
       }else if(ch=='(') val=1;
       else if (ch==')') val=-1;
       update(1,pos,n,val-a[pos]);
       a[pos]=val;
       write:
       if(t[1].min<0||query(1,n)!=0) cout<<-1<<' ';
       else cout<<t[1].max<<' ';
    }
    return 0;
}

Codeforces 1263E - Editor 题解

解法 #

Code #