cp-problems

かっこいい電車

解説

いくつかの解法が考えられます（平衡二分探索木で区切りを管理するなど）が，ここでは和の BIT (Binary Indexed Tree) を 2 つ使った解法を示します．2 つとも，BIT の各要素と各車両を対応させます．

1 つ目は，車両のまとまりを管理する BIT です．

はじめに，BIT の各要素を \(1\) で初期化します．

connect query では，車両 \(i + 1\) に対応する番号の要素を \(0\) に，

separate query では，車両 \(i + 1\) に対応する番号の要素を \(1\) にします．

こうすることで，BIT の \({\rm sum}(i)\) を呼び出したときに，「車両 \(i\) が含まれる車両のまとまりが，左から何番目のまとまりか」が \(O(\log N)\) で求まります．

また，\({\rm sum}(i)\) を二分探索することで，特定のまとまりの先頭の車両と後尾の車両の番号が求まります．これは愚直にやると \(O(\log^2 N)\) ですが，\(O(\log N)\) に落とすこともできます．

2 つ目は，車両のかっこよさを保存するための BIT です．

最初に，BIT の各要素を \(A_i\) で初期化します．

remodel query では，車両の番号の要素を \(1\) 増やします．

最後に，attractiveness query では，上述の二分探索によってその車両が含まれる車両のまとまりの範囲を取得し，2つ目の BIT で sum の差をとることでこたえることができます．

計算量は \(O((N + Q) \log N)\) です．

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0, _##i = (n); i < _##i; ++i)

struct BIT {
    vector<ll> data;

    BIT() {}
    BIT(ll n) : data(n + 1) {
        fill(data.begin(), data.end(), 0);
        data[0] = n;
    }

    void add(ll pos, ll val) {
        pos++;
        while (pos <= data[0]) {
            data[pos] += val;
            pos += pos & -pos;
        }
    }
    ll sum(ll pos) {
        if (pos <= 0) return 0;
        ll res = 0;
        while (pos > 0) {
            res += data[pos];
            pos -= pos & -pos;
        }
        return res;
    }
    ll sum(ll l, ll r) { return sum(r) - sum(l); }

    ll lower_bound(ll val) {
        if (val <= 0) return 0;
        ll index = 0;
        for (ll d = 1 << ll(log2(data[0])); d > 0; d /= 2) {
            if (index + d <= data[0] && data[index + d] < val) {
                val -= data[index + d];
                index += d;
            }
        }
        return index;
    }
};

struct GC {
    int size;
    BIT bit;

    GC(int n) : bit(n), size(n) {
        for (int i = 1; i <= bit.data[0]; i++) { bit.data[i] = i & -i; }
    }

    int group_index(int index) { return bit.sum(index + 1) - 1; }
    int dist(int x, int y) { return abs(group_index(x) - group_index(y)); }

    int begin(int group_index) { return bit.lower_bound(group_index + 1); }
    int end(int group_index) { return bit.lower_bound(group_index + 2); }
    int group_size(int group_index) { return end(group_index) - begin(group_index); }

    void group(int index) {
        int s = -(bit.sum(index + 2) - bit.sum(index + 1));
        bit.add(index + 1, s);
        size += s;
    }
    void cut(int index) {
        int s = !(bit.sum(index + 2) - bit.sum(index + 1));
        bit.add(index + 1, s);
        size += s;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    int A, B;
    BIT bit(N);
    GC gc(N);
    rep(i, N) cin >> A, bit.add(i + 1, A);
    rep(i, Q) {
        cin >> A >> B;
        if (A == 1) {
            gc.group(B - 1);
        } else if (A == 2) {
            gc.cut(B - 1);
        } else if (A == 3) {
            bit.add(B, 1);
        } else {
            int index = gc.group_index(B - 1);
            cout << bit.sum(gc.end(index)) - bi.sum(gct.begin(index)) << endl;
        }
    }
}