概要

この問題は、一列に並んだグラスに上からシャンパンを注ぎ、溢れた分が下のグラスへと順に流れ落ちていくシミュレーションを高速に行う問題です。

素朴にシミュレーションを行うと、すでに満杯になったグラスを何度も走査することになり、実行時間制限に間に合いません。そこで、Union-Find（DSU: Disjoint Set Union） を用いて「まだ満杯になっていない次のグラス」を高速に検出することで、効率的にシミュレーションを行います。

---

考察

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

最も単純な方法は、シャンパンを注ぐたびに \(1\) 段目のグラスから順に見ていき、容量を超えたら超過分を次の段に加える、という操作を繰り返すことです。

しかし、すでに多くのグラスが満杯になっている状態で大量のシャンパンを注ぐと、毎回「すでに満杯のグラス」を1つずつ順番にスキップしていくことになります。 最悪の場合、1回の注ぐ操作に \(O(N)\) の時間がかかり、クエリ数を \(Q\) とすると全体の計算量は \(O(NQ)\) となります。 \(N, Q \le 2 \times 10^5\) であるため、これでは実行時間制限（TLE）になってしまいます。

高速化の鍵：「次に満杯になっていないグラス」へのジャンプ

高速化のために、「すでに満杯になったグラスを高速にスキップする」 方法を考えます。

グラス \(i\) が満杯になったとき、次にグラス \(i\) にシャンパンが流れ込んできたら、それは即座に「グラス \(i\) より下にある、まだ満杯になっていない最も近いグラス」へと流れるべきです。

このような「グループの代表元（この場合は、次に空きがある最も近いグラス）を管理する」構造には、Union-Find（DSU） が最適です。

具体的には、以下のように管理します。 - グラス \(i\) が満杯になった瞬間、グラス \(i\) とグラス \(i+1\) を連結（unite）する。 - 連結する際、常にインデックスが大きい方（より下段のグラス）が根（代表元）になるようにマージする。

このようにすると、グラス \(i\) にシャンパンが注がれた（または流れ込んできた）とき、DSUの find(i) を呼び出すだけで、次にシャンパンを受け止めるべき「まだ満杯になっていない最小のインデックスを持つグラス」をほぼ \(O(1)\) 時間で特定することができます。

---

アルゴリズム

1. DSUの初期化

サイズ \(N + 2\) のDSUを用意します。 - \(1\) から \(N\) までの要素は各グラスに対応します。 - \(N + 1\) は「タワーの底（地面）」を表す番兵です。最下段のグラスから溢れたシャンパンを受け止める役割を持ち、容量は無限大（または単に溢れた分を捨てる場所）とみなします。 - 初期状態では、各グラスは満杯ではないため、それぞれが独立した集合の根となります。

2. 操作 \(1\)（注ぐ）の処理

\(1\) 段目に \(V\) ミリリットルのシャンパンを注ぐ指示が来たら、以下の手順を繰り返します。

1. curr = dsu.find(1) により、現在シャンパンが流れ込むべきグラスのインデックスを取得します。
2. curr <= n かつ \(V > 0\) である限り、以下を実行します：
   • グラス curr の現在の空き容量 space = C[curr] - A[curr] を計算します。
   • ケースA： \(V \ge \text{space}\) の場合（グラスが満杯になる）
     • グラス curr は満杯になります。
     • \(V\) から space を引き（残りのシャンパンの量を更新）、A[curr] = C[curr] とします。
     • グラス curr が満杯になったため、dsu.unite(curr, curr + 1) を行い、次のグラスへと経路を繋ぎます。
     • curr = dsu.find(curr) で次に注ぐべきグラスを更新します。
   • ケースB： \(V < \text{space}\) の場合（グラスが満杯にならない）
     • グラス curr に \(V\) をすべて注ぎきることができます。
     • A[curr] に \(V\) を加え、\(V = 0\) とします。
     • ループを終了します。

3. 操作 \(2\)（問い合わせ）の処理

グラス \(k\) に入っている現在の量 A[k] をそのまま出力します。

---

計算量

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

• 各グラスが「満杯になる」というイベントは、タワー全体で高々 \(N\) 回しか発生しません。
• グラスが満杯になったときにのみ dsu.unite が呼ばれるため、unite の総実行回数は高々 \(N\) 回です。
• したがって、操作 \(1\) における while ループの合計回転数は、すべてのクエリを通して高々 \(N + Q\) 回に抑えられます。
• DSUの各操作（find, unite）は、アッカーマン関数の逆関数 \(\alpha\) を用いて \(O(\alpha(N))\)（ほぼ定数時間）で行えるため、全体の時間計算量は \(O((N + Q) \alpha(N))\) となり、極めて高速に動作します。

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

• グラスの容量配列 C、現在のシャンパン量配列 A、およびDSUの親ノードを管理する配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

• DSUのマージ方向の強制: 通常のDSUでは木の高さを低く保つために「サイズによる結合（union by size）」などを行いますが、本問題では「常にインデックスが大きい方を親にする」必要があります。 unite 関数内で、必ず root_i < root_j のときに parent[root_i] = root_j となるように実装します。

• インデックス \(N+1\) の番兵: 最下段（\(N\) 段目）のグラスが満杯になったとき、さらに下の \(N+1\) とマージします。配列の範囲外アクセスを防ぐため、DSUのサイズは \(N+2\) で確保しておく必要があります。

• 入出力の高速化: クエリ数が多いため、C++では std::cin の高速化（ios_base::sync_with_stdio(false); cin.tie(NULL);）および改行時の std::endl（バッファフラッシュが発生する）の代わりに "\n" を使用することが推奨されます。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// Disjoint Set Union (DSU) to find the next available non-full glass
struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // Always point to the larger index (towards the bottom of the tower)
            if (root_i < root_j) {
                parent[root_i] = root_j;
            } else {
                parent[root_j] = root_i;
            }
        }
    }
};

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    vector<long long> A(n + 1, 0); // Current amount of champagne in each glass
    DSU dsu(n + 2); // Size n + 2 to handle the boundary case at level n + 1

    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            long long v;
            cin >> v;
            int curr = dsu.find(1);
            while (curr <= n && v > 0) {
                long long space = C[curr] - A[curr];
                if (v >= space) {
                    v -= space;
                    A[curr] = C[curr];
                    dsu.unite(curr, curr + 1);
                    curr = dsu.find(curr);
                } else {
                    A[curr] += v;
                    v = 0;
                }
            }
        } else {
            int k;
            cin >> k;
            cout << A[k] << "\n";
        }
    }

    return 0;
}

---

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