CF Round #223 Div.1 C. Sereja and Brackets

Codeforces Round #223 Div.1 C. Sereja and Brackets

Problem - D - Codeforces

"("と")"のみからなる文字列が与えられる。クエリとしてある区間[l, r]が与えられるので、その区間の中で、"("と")"のペアがうまくつくれるようなものは何個あるかを答える問題。愚直に数えるともちろん間に合わないので、セグメント木を使う。今回は、各ノードに構造体{x, l, r}を持たせ、xがそれまでに完成しているペアの数、l がまだ使っていない")"の数、rがまだ使っていない"("の数とした。ノードを更新するときは、ある親ノードから見て、左の子のrと、右の子のlがどちらも１以上なら、その小さい方の分だけ繰り上がりの要領でxを増加させて、その分lとrを減らす。xは完成しているものの数なのでそのまま加算すればよい。常に左の子のrと右の子のlを考慮して計算すれば、計算の順序は変えても問題ない。

#include "bits/stdc++.h"
using namespace std;
#define OUT(x)                cout << #x << " = " << x << endl; 
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
#define rer(i, l, r)          for (int (i) = (int)(l); (i) <= (int)(r); (i)++)
#define reu(i, l, r)          for (int (i) = (int)(l); (i) < (int)(r); (i)++)
#define each(i, v)            for (auto i : v)
#define all(x)                (x).begin(), (x).end()
#define rall(x)               (x).rbegin(), (x).rend()
#define pb(x)                 push_back(x)
#define bp(x)                 __builtin_popcount(x)
#define mp(x, y)              make_pair((x), (y))
#define fi                    first
#define se                    second
#define setp(x)               setprecision(x)
#define mset(m, v)            memset(m, v, sizeof(m))
#define sz(x)                 (int)(x.size())
static const int INF        = 0x3f3f3f3f;
static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD        = 1000000007;
static const double PI      = 3.141592653589793238462643383279;

//#define int                   long long

typedef vector<double>        vd;
typedef vector<string>        vs;
typedef vector<bool>          vb;
typedef vector<int>           vi;
typedef pair<int, int>        pii;
typedef vector<pii>           vpii;

template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; }
template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int _x; scanf("%d", &_x); return _x; }
long long lin() {long long _x; scanf("%lld", &_x); return _x; };

struct P { int x, l, r; };

struct SegmentTree {
        vector<P> data;
        int n;
        SegmentTree(int x) {
                n = 1;
                while (n < x) n *= 2;
                data.resize(2 * n);
                for (int i = 0; i < 2 * n; i ++) data[i] = {0, 0, 0}; //何も入っていないところはすべて0にしておけばよい
        }
        P merge(P datal, P datar) { //左の子と右の子で親をつくる
                int newx = 0;
                int add = min(datal.r, datar.l);
                datal.r -= add;
                datar.l -= add;
                newx += add;
                return { datal.x + datar.x + newx, datal.l + datar.l, datal.r + datar.r };
        }
        // update k th element
        void update(int k, P p) {
                k += n - 1;
                data[k] = p;
                while (k > 0) {
                        k = (k - 1) / 2;
                        data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]);
                }
        }
        // calculate [l, r))
        P query(int a, int b) { return query(a, b, 0, 0, n); }
        P query(int a, int b, int k, int l, int r) {
                if (r <= a || b <= l) return {0, 0, 0};
                if (a <= l && r <= b) return data[k];
                int m = (l + r) / 2;
                return merge(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r));
        }
};
             
signed main() { 
        string s;
        cin >> s;
        int n = sz(s);
        SegmentTree st(n);
        rep(i, n) {
                if (s[i] == '(') st.update(i, {0, 0, 1}); //"("ならrのみ1
                else st.update(i, {0, 1, 0});             //")"ならlのみ1
        }
        int q;
        cin >> q;
        rep(i, q) {  // [l, r)に注意する
                int l, r;
                cin >> l >> r;
                l --;
                P ans = st.query(l, r);
                cout << ans.x * 2 << endl;
        }
        return 0;
}               
         

構造体とか使わずにもっと簡潔に書けるかもしれないけど、割と直感的に書けたのでいいかな。