ICPC 2019 Asia Yokohama Regional H Parentheses Editor

問題ページ
'('，')'をそれぞれ+1，-1に言い換える．区間の部分文字列が正しい括弧列であるとは，区間の始点までの累積和と終点までの累積和がで一致していて，区間の間に累積和が 未満の点が存在しないことと等しい．

ある')'に対応する，部分文字列が正しい括弧列であるものを数えたい．累積和が 未満の点より遅く，累積和が である の個数を数えればよい．
累積和が の点の集合を map<ll,vector>，seg[x] = (累積和がである点のうち最も遅いもの) としたセグ木を持っておく．累積和が 未満の点のうち最も遅いものは，セグ木の区間の最大で求められる．累積和が の点の集合のうち，累積和が 未満の点より遅いものを二分探索で求められる．

削除に対応するには，行った操作をstackの要領で覚えておき，削除する際はこれに応じて戻せばよい．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long int;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) (x.begin(), x.end())  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
ll INF = 1LL<<60;  
  
template<typename Monoid>  
struct segtree {  
    using T = typename Monoid::T;  
    int n;  
    vector<T> dat;  
  
    segtree(int n0) {  
        n = 1;  
        while(n < n0) n <<= 1;  
        dat.assign(n*2, Monoid::id());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
    }  
  
    T query(int a, int b) {  
        T l = Monoid::id(), r = Monoid::id();  
        for(a+=n, b+=n; a<b; a>>=1, b>>=1) {  
            if(a&1) l = Monoid::op(l, dat[a++]);  
            if(b&1) r = Monoid::op(dat[--b], r);  
        }  
        return Monoid::op(l, r);  
    }  
    void update(int i, T v) {  
        i += n;  
        dat[i] = v;  
        while(i >>= 1) {  
            dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
        }  
    }  
};  
  
template<typename Tp>  
struct max_monoid {  
    using T = Tp;  
    static constexpr Tp id() { return -INF; }  
    static Tp op(const Tp &a, const Tp &b) { return max(a, b); }  
};  
  
signed main() {  
    string s;  
    cin >> s;  
    const ll n = s.size();  
  
    segtree<max_monoid<ll>> seg(n*2+1);  
  
    string t = "";  
    ll x = 0, ans = 0;  
    map<ll,vector<ll>> mp, mp2;  
    REP(i, n) {  
        if(s[i]=='(') {  
            x++;  
            mp[x].push_back(i);  
            t += s[i];  
        } else if(s[i]==')') {  
            ll lb = seg.query(0, x+n-1);  
            // mp[x]のlbより大きいやつの個数  
            ll num = mp[x].size() - (lower_bound(mp[x].begin(), mp[x].end(), lb) - mp[x].begin());  
            ans += num;  
            x--;  
            seg.update(x+n, i);  
            mp2[x].push_back(i);  
            t += s[i];  
        } else {  
            if(t.back() == '(') {  
                mp[x].pop_back();  
                x--;  
            } else {  
                mp2[x].pop_back();  
                seg.update(x+n, (mp2[x].size()?mp2[x].back():-INF));  
                x++;  
                ll lb = seg.query(0, x+n-1);  
                // mp[x]のlbより大きいやつの個数  
                ll num = mp[x].size() - (lower_bound(mp[x].begin(), mp[x].end(), lb) - mp[x].begin());  
                ans -= num;  
            }  
            t.pop_back();  
        }  
  
        cout << ans << "\n";  
    }  
    cout << flush;  
}