MUJIN プログラミングチャレンジ D - 括弧列 / Parenthesis Sequence

問題

mujin-pc-2016.contest.atcoder.jp

解法

正しい括弧列は, 「'(' の数が ')' の数を下回ることなく進んでいき, 最終的に '(' と ')' の数が等しくなる文字列」と解釈することも出来ます。これ結構よく出るので覚えておいたほうが良いです。

そう考えると, '?' があったら, できるだけ前の方に '(' を配置していくと考えるのが明らかに最適です。また, '(' の数が ')' の数を下回ることがないかは, RMQ で高速に判定できます。
よって, 雰囲気としては以下のような解法です。

• '?' をすべて '(' に置き換えた場合の RMQ, ')' に置き換えた場合の RMQ を作っておく
• クエリには以下のように対応する(区間は [l, r) で持つ)
  • 累積和計算しておけば, '?' に対して, いくつを '(' にすれば良いかがわかるので, それを求める
  • '(' で補完する最後の '?' の位置を rh とする。すると, [l, rh] の RMQ 値が [l, l] を下回ることなく, また [rh+1, r) の RMQ 値が [r, r] を下回ることがないようなら OK, そうでないなら NG

ちょっと区間に疑問を持った人がいるかもしれませんが, 多分合ってます。
まず [l, l] と [l, rh] を比較するのはそんなに違和感ないと思いますが, そうするんだったら [rh+1, r) と [r-1, r-1] を比較するのが自然に見えます。ですが, 今回の実装では height[i+1] = height[i] + diff とやる感じになる(height が '(' と ')' の数の差)ので, 区間 [l, r) の最終的な height は, height[r-1] ではなく height[r] にメモされています。それを考えると上が正しそうです。

こういう ±1 考えるの本当に苦手なんですがなにか良い方法合ったら教えて欲しいです(小技みたいのでも良いので本当に教えて欲しい)。

// セグメント木(RMQ 対応)
// update: k 番目の値を a に変更
// query: [l, r) の区間の最大値を求める
template<typename T>
struct ST {
    vector<T> seg;
    int size;
    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(2*size-1, numeric_limits<T>::max());
    }
    inline T merge(T x, T y) {
        return min(x, y);
    }
    void update(int k, T a) {
        k += size-1;
        seg[k] = a;
        while (k > 0) {
            k = (k-1)/2;
            seg[k] = merge(seg[k*2+1], seg[k*2+2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return numeric_limits<T>::max();
        if (a <= l && r <= b) return seg[k];
        T vl = query(a, b, k*2+1, l, (l+r)/2);
        T vr = query(a, b, k*2+2, (l+r)/2, r);
        return merge(vl, vr);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string s;
    cin >> s;
    // seg1: ? を ( に変える
    // seg2: ? を ) に変える
    ST<int> segl(N+10), segr(N+10);
    vector<int> lp(N+10), rp(N+10), qp(N+10);
    int lt = 0, rt = 0;
    segl.update(0, 0); segr.update(0, 0);
    for (int i = 0; i < N; i++) {
        lp[i+1] = lp[i], rp[i+1] = rp[i], qp[i+1] = qp[i];
        if (s[i] == '(') lp[i+1]++, lt++, rt++;
        if (s[i] == ')') rp[i+1]++, lt--, rt--;
        if (s[i] == '?') qp[i+1]++, lt++, rt--;
        segl.update(i+1, lt); segr.update(i+1, rt);
    }
    auto f = [&] (int l, int r) {
        int num = r-l;
        if (num%2) return false;
        int ln = num/2 - (lp[r]-lp[l]), rn = num/2 - (rp[r]-rp[l]);
        if (ln < 0 || rn < 0) return false;
        if (ln == 0) {
            if (segr.query(l, r+1) >= segr.query(r, r+1)) return true;
            else return false;
        }
        int mp = qp[l]+ln;
        int lh = l, rh = N;
        while (rh-lh > 1) {
            const int med = (lh+rh)/2;
            if (qp[med] >= mp) rh = med;
            else lh = med;
        }
        if (rh == N) {
            if (segl.query(l, r+1) >= segl.query(l, l+1)) return true;
            else return false;
        }
        if (segl.query(l, rh+1) >= segl.query(l, l+1) && segr.query(rh+1, r+1) >= segr.query(r, r+1)) return true;
        return false;
    };
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        if (f(l-1, r)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}