D - 一次元オセロ (1D Othello) パ研合宿コンペティション 2日目

D - 一次元オセロ (1D Othello)

kmjpさんの実装を参考にしました
Submission #3867975 - パ研合宿コンペティション 2日目

解法
白黒を区間として持てばひっくり返すのが楽です。
操作中の区間は高々N+1個であり、消える区間は端であるため、dequeを使えば実装できます。
deque{その区間の色,その区間の先頭index}とすれば、操作ごとのひっくり返される範囲が分かります。
さらに、binary indexed treeを使えば、いもす法的に範囲に加算が出来るため
ある石がひっくり返された回数が分かります。

注意点
左右に追加されるため、左端のindexを200000等として余裕を持つ
クエリはソートできる
ひっくり返されたdequeの要素は削除するが、一回の操作につき高々1つしか削除されないため高速

Submission #3874808 - パ研合宿コンペティション 2日目

template<class T=int> struct BIT {
    vector<T> dat;
    int n;
    BIT(int size) : n(size + 1) {
        dat.resize(n);
    }
    //閉
    void add(int hei, T v) {
        hei++;
        while (hei < n)dat[hei] += v, hei += (hei & -hei);
    }
    //開区間
    T operator()(int kai) {
        if (kai <= 0)return 0;
        T res = 0;
        while (kai) res += dat[kai], kai -= kai & -kai;
        return res;
    }
    T sum(int l, int r) {
        return operator()(r) - operator()(l);
    }
};

signed main() {
    string s;
    cin >> N >> s >> M;
    deque<pair<char, int>> dq;
    vc D(M), C(M);
    rep(i, M)cin >> D[i] >> C[i];
    vi L(M + 3), R(M + 3);
    L[0] = 2 * 101010;
    R[0] = L[0] + N - 1;
    rep(i, M) {
        L[i + 1] = L[i] - (D[i] == 'L');
        R[i + 1] = R[i] + (D[i] == 'R');
    }
    BIT<int> bt(6 * 101010);
    //左からの合計が偶数なら白、奇数なら黒となるようにBITに加算
    rep(i, N) {
        if (i is 0) {
            dq.push_back({s[i], L[0]});
            //Bならひっくり返す必要がある。
            if (s[i] == 'B') bt.add(L[0], 1);
        } else if (s[i - 1] != s[i]) {
            dq.push_back({s[i], L[0] + i});
            bt.add(L[0] + i, 1);
        }
    }
    //時間 pos i
    vvp (ques, 2 * 101010, 0);
    //using P = pair<int,int>;
    //vector<P> ques(2 * 101010 , vector<P>(0));

    cin >> Q;
    rep(i, Q) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        ques[a].eb(b, i);
    }
    vc res(Q);
    rep(i, M) {
        if (D[i] == 'L') {
            //同じ色なら
            if (C[i] == dq.front().F) {
                if (C[i] == 'B')bt.add(dq.front().S, 1);
                dq.front().S = L[i + 1];
                //違う色でひっくり返す相手がいない
            } else if (dq.size() == 1) {
                if (C[i] == 'B')bt.add(dq.front().S, 1);
                dq.pf({C[i], L[i + 1]});
                //違う色なのでひっくり返す
            } else {
                //左
                if (C[i] == 'W')bt.add(dq.front().S, 1);
                dq.pop_front();
                //右側
                bt.add(dq.front().S, 1);
                dq.front().S = L[i + 1];
            }
            if (C[i] == 'B')bt.add(L[i + 1], 1);
        } else {
            if (C[i] == dq.back().F) {
                //;
            } else if (dq.size() == 1) {
                dq.pb({C[i], R[i + 1]});
                //WB とわず　ひっくり返す
                bt.add(R[i + 1], 1);
            } else {
                // 1
                //WBB
                // 1
                //BWW
                //どちらにせよ真ん中に1足せば良い
                bt.add(dq.back().S, 1);
                dq.pop_back();
            }
        }
        for (auto &&e :ques[i]) {
            res[e.S] = "WB"[bt(L[i + 1] + e.F + 1) % 2];
        }
    }
    rep(i, Q) {
        cout << res[i] << endl;
    }
    return 0;
}