概要

この問題は、商店街の店舗の営業状態と売上を管理し、区間加算・店舗の閉店・累積閉店売上のクエリを高速に処理する問題です。 営業状態の管理、営業中店舗の二分探索、および累積売上の計算を、3つの BIT（Binary Indexed Tree / フェニック木） を用いて効率的に処理します。

---

考察

素朴なアプローチとその限界

クエリごとに配列を愚直に更新する方法を考えてみます。 - 操作 1: 区間 \([l, r]\) の営業中の店舗すべてに \(x\) を加算する。最悪で \(O(N)\) かかります。 - 操作 2: 店舗 \(p\) を閉店にする。\(O(1)\) です。 - 操作 3: 営業中の \(k\) 番目の店舗 \(j\) を探し、\([1, j]\) の閉店済み店舗の売上を合計する。最悪で \(O(N)\) かかります。

これでは全体の計算量が \(O(QN)\) となり、 \(N, Q \le 10^5\) の制約下では実行時間制限に間に合いません（TLE）。クエリあたり \(O(\log N)\) 程度で処理するデータ構造が必要です。

重要な観察：閉店した店舗の売上は「固定」される

操作 1 では「営業中の店舗のみ」に売上を加算します。一見すると、閉店した店舗を避けて加算を管理する必要があるため、複雑な区間更新が必要に見えます。

しかし、「閉店した店舗の売上は、閉店した瞬間にその値で確定し、以降は一切変化しない」 という点に注目します。 店舗 \(p\) が営業している間は、区間加算（操作 1）の影響をすべて受けます。そして、店舗 \(p\) が閉店する瞬間に、その時点での売上を計算して記録してしまえば、それ以降に操作 1 が行われても、記録した売上を変更する必要はありません。

したがって、営業中の店舗に対する区間加算は、閉店している店舗も含めて「位置 \(i\) に対する累積加算額」としていもす法のように管理して問題ありません。店舗 \(p\) が閉店する瞬間に、初期売上 \(V_p\) にその時点での累積加算額を足すことで、正しい「閉店時の売上」を \(O(\log N)\) で求めることができます。

必要な情報の整理

クエリを高速に処理するために、以下の3つの情報をデータ構造で管理します。

1. 各位置における累積加算額（操作 1 の区間加算を管理）
2. 各店舗の営業状態（営業中なら 1、閉店なら 0）
3. 閉店した店舗の確定売上（閉店した店舗の位置に売上を記録）

これらはすべて、値の追加と区間和（または一点取得）を高速に行える BIT（Binary Indexed Tree） を用いることで、効率的に管理できます。

---

アルゴリズム

3つの BIT（add_bit, active_bit, closed_val_bit）を用意します。

1. 初期化

• add_bit: すべて \(0\) で初期化します（サイズ \(N+1\)）。
• active_bit: すべての店舗が営業中なので、各位置 \(1 \le i \le N\) に \(1\) を加算します。
• closed_val_bit: すべて \(0\) で初期化します。

2. 各操作の処理

操作 1 (1 l r x)

営業中の店舗の売上を \(x\) 加算します。 add_bit を用いて、区間 \([l, r]\) に \(x\) を加算する「いもす法」を行います。 - add_bit.add(l, x) - add_bit.add(r + 1, -x) これにより、任意の店舗 \(i\) がこれまでに受けた累積加算額は add_bit.query(i) で取得できるようになります。

操作 2 (2 p)

店舗 \(p\) が閉店します。 1. 店舗 \(p\) の現時点での売上を計算します。 $\(\text{確定売上} = V_p + \text{add\_bit.query}(p)\)\( 2. 計算した確定売上を `closed_val_bit` の位置 \)p\( に記録します。 - `closed_val_bit.add(p, 確定売上)` 3. 店舗 \)p\( の状態を営業中から閉店に変更します。 - `active_bit.add(p, -1)` （値を \)1\( から \)0$ にする）

操作 3 (3 k)

1. 営業中の \(k\) 番目の店舗の番号 \(j\) を求める active_bit は営業中の店舗の位置に \(1\) が立っている配列です。したがって、「累積和がちょうど \(k\) になる位置 \(j\)」が求める店舗の番号になります。 これは BIT 上での二分探索（find_kth）を用いることで、\(O(\log N)\) で高速に求めることができます。
2. 累積閉店売上額を出力する 店舗 \(1\) から \(j\) までの閉店済み店舗の売上の合計は、closed_val_bit の区間 \([1, j]\) の総和に等しいです。
   • closed_val_bit.query(j) を出力します。

---

計算量

• 時間計算量: \(O((N + Q) \log N)\)

  • 初期化において、active_bit への要素の追加に \(O(N \log N)\) かかります。
  • 各クエリ（操作 1, 2, 3）は、BIT の更新・取得・二分探索のみを行うため、それぞれ \(O(\log N)\) で処理されます。
  • よって、全体で \(O((N + Q) \log N)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • 長さ \(N\) の配列 \(V\) と、サイズ \(N\)（または \(N+1\)）の BIT を3つ保持するため、空間計算量は \(O(N)\) です。

---

実装のポイント

BIT 上の二分探索 (find_kth)

操作 3 で「累積和が \(k\) になる位置」を求める際、通常の二分探索（std::lower_bound などと BIT のクエリの組み合わせ）を行うと \(O(\log^2 N)\) かかってしまいます。 BIT の構造を利用した二分探索（コード中の find_kth 関数）を実装することで、1回の探索を \(O(\log N)\) で行うことができます。これは、BIT のインデックスを \(2\) のべき乗の大きい方から試していくことで実現できます。

データの型

売上の累積値は \(2^{63}\) 未満になることが保証されているため、C++ では long long 型（64ビット符号付き整数）を使用する必要があります。add_bit と closed_val_bit は long long 型で、active_bit は店舗の存在（\(0\) または \(1\)）のみを扱うため int 型で実装します。

ソースコード

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
struct BIT {
    int n;
    vector<T> data;
    BIT(int n) : n(n), data(n + 1, 0) {}
    void add(int i, T x) {
        for (; i <= n; i += i & -i) data[i] += x;
    }
    T query(int i) {
        T sum = 0;
        for (; i > 0; i -= i & -i) sum += data[i];
        return sum;
    }
    int find_kth(int k) {
        int idx = 0;
        int h = 1;
        while (h <= n) h <<= 1;
        h >>= 1;
        for (int i = h; i > 0; i >>= 1) {
            if (idx + i <= n && data[idx + i] < k) {
                idx += i;
                k -= data[idx];
            }
        }
        return idx + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<long long> v(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    BIT<long long> add_bit(n + 1);
    BIT<int> active_bit(n);
    BIT<long long> closed_val_bit(n);

    for (int i = 1; i <= n; ++i) {
        active_bit.add(i, 1);
    }

    for (int qi = 0; qi < q; ++qi) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            add_bit.add(l, x);
            add_bit.add(r + 1, -x);
        } else if (type == 2) {
            int p;
            cin >> p;
            long long cur_val = v[p] + add_bit.query(p);
            closed_val_bit.add(p, cur_val);
            active_bit.add(p, -1);
        } else if (type == 3) {
            int k;
            cin >> k;
            int j = active_bit.find_kth(k);
            long long ans = closed_val_bit.query(j);
            cout << ans << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。