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

いやぁこれは頭良いっす…

問題

codeforces.com

解法

セグメント木を使って解くことが出来ます。

2 つの区間を合併する時, 各区間の valid な括弧列の長さを ok, それ以外で '(' の数を open, ')' の数を close とすると, valid な括弧列は崩しても得をしないので, 左側の括弧列情報を left, 右側の括弧列情報を right として,

        int tmp = min(left.open, right.close);
        ret.ok = left.ok + right.ok + 2*tmp;
        ret.open = left.open + right.open - tmp;
        ret.close = left.close + right.close - tmp;

という関係が成り立ちます。あとはセグメント木を使って頑張るだけです。

struct bracket {
    int ok;
    int open;
    int close;
    bracket() : ok(0), open(0), close(0) {}
    bracket(int ok, int open, int close) : ok(ok), open(open), close(close) {}
};

struct ST {
    vector<bracket> seg;
    int size;
    ST(const string& s) {
        int n = s.size();
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1);
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') seg[i+size-1].open = 1;
            else seg[i+size-1].close = 1;
        }
        for (int i = size-2; i >= 0; i--) {
            seg[i] = merge(seg[i*2+1], seg[i*2+2]);
        }
    }
    inline bracket merge(const bracket& left, const bracket& right) {
        bracket ret;
        int tmp = min(left.open, right.close);
        ret.ok = left.ok + right.ok + 2*tmp;
        ret.open = left.open + right.open - tmp;
        ret.close = left.close + right.close - tmp;
        return ret;
    }
    bracket query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return bracket();
        if (a <= l && r <= b) return seg[k];
        bracket vl = query(a, b, k*2+1, l, (l+r)/2);
        bracket vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    bracket query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int m;
    cin >> m;
    ST seg(s);
    while (m--) {
        int l, r;
        cin >> l >> r;
        l--;
        cout << seg.query(l, r).ok << endl;
    }
    return 0;
}

クエリ系 -> セグメント木かな -> 区間を合併するとしたらどうなるんだろうか みたいな発想はあった方が良かったかも。

それとは関係ないんだけど, セグメント木, merge っていう関数を作って query, update をやるようにすると見通しが良くなってデバッグがしやすいので結構良いと思います。