概要

一列に並んだ \(N\) 個のグラスに対して、シャンパンを注ぐ操作（溢れは下の段へ流れる）と、指定段のシャンパン量を問い合わせる操作を効率的に処理する問題です。

考察

素朴なアプローチの問題点

素朴な方法では、シャンパンを注ぐたびに1段目から順にオーバーフローを処理します。最悪の場合、1回の注入操作で全 \(N\) 段を走査するため、\(Q\) 回の操作全体で \(O(NQ)\) かかり、\(N = Q = 2 \times 10^5\) のとき \(4 \times 10^{10}\) 回の処理となりTLEします。

重要な気づき：グラスは一度満杯になったら戻らない

この問題ではシャンパンを注ぐ操作のみで、グラスからシャンパンを抜く操作はありません。つまり：

• グラスのシャンパン量は単調非減少
• 一度満杯（\(C_i\) に達した）グラスは、永遠に満杯のまま

この性質により、満杯のグラスを何度も再処理する必要がなくなります。

解決策：フロンティアポインタ

「まだ満杯でない最初のグラス」を指すポインタ front を管理します。

• front より前のグラスはすべて満杯（容量 \(C_i\) ちょうど）
• シャンパンを注ぐと、満杯のグラスを素通りして front 番目のグラスに直接到達する

具体例：\(C = [3, 5, 2, 4]\) のとき

1. 最初 front = 0、\(V = 10\) を注ぐ → glass[0] に 10 が入る → 容量 3 を超過、7 が溢れる → glass[0] = 3（満杯）、glass[1] += 7 → glass[1] = 7 > 5、2が溢れる → glass[1] = 5（満杯）、glass[2] += 2 → glass[2] = 2 ≤ 2（ちょうど満杯）→ front = 3
2. 次に \(V = 1\) を注ぐ → front = 3 なので glass[3] += 1 → glass[3] = 1 ≤ 4 → 溢れない

アルゴリズム

1. front = 0（最初の非満杯グラスのインデックス）を初期化
2. 操作1（注ぐ）のとき：
   • front >= N ならすべて満杯で、シャンパンは失われる
   • そうでなければ glass[front] += V
   • front の位置から下方向へ、溢れが止まるまでカスケード処理
   • 新たに満杯になったグラスの分だけ front を進める
3. 操作2（問い合わせ）のとき：
   • glass[k-1] の値を出力

ポイント：各グラスは高々1回だけ「満杯になる」処理を受けるため、全操作を通じたカスケード処理のステップ数の合計は最大 \(N\) 回です。

計算量

• 時間計算量: \(O(N + Q)\)
  • カスケード処理は全操作を通じて合計 \(O(N)\)（各グラスが満杯になるのは1回のみ：償却解析）
  • 各クエリの読み取り・出力は \(O(1)\)
• 空間計算量: \(O(N)\)（グラスの状態を保持する配列）

実装のポイント

• front ポインタにより、満杯グラスのスキップを \(O(1)\) で実現

• カスケードのwhileループ内で i + 1 < N の境界チェックを忘れないこと（最下段から溢れたシャンパンは消失）

• 出力を一括で行う（sys.stdout.write でまとめて出力）ことで、Pythonでの出力のオーバーヘッドを削減

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    
    # glass[i] = current amount in glass i
    glass = [0] * N
    
    # We need to efficiently handle pouring.
    # Key insight: when we pour V into glass 0, overflow cascades down.
    # Naive simulation: pour into glass[0], then for each glass from top to bottom,
    # if glass[i] > C[i], overflow = glass[i] - C[i], glass[i] = C[i], glass[i+1] += overflow.
    # 
    # Worst case: Q pours each cascading through N glasses = O(NQ) which is 4*10^10 -- too slow.
    #
    # Optimization: track a "frontier" pointer. Once a glass is full, it stays full until...
    # Actually, glasses only get more champagne (never less), so once a glass is full it stays full.
    # 
    # We can maintain a pointer `front` = the first glass that is NOT full.
    # All glasses before `front` are full (glass[i] == C[i]).
    # When we pour V into glass 0:
    #   - Since glasses 0..front-1 are all full, the V ml will cascade through all of them
    #     and arrive at glass[front] (adding to whatever is there).
    #   - Then we need to check if glass[front] overflows, and cascade from there.
    #
    # So effectively: glass[front] += V, then cascade from front onwards.
    # The cascade from front will fill some glasses and stop.
    # Each glass can become full at most once across all operations, so total cascade steps = O(N) amortized.
    
    front = 0  # index of first non-full glass (or N if all full)
    
    out = []
    
    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            V = int(line[1])
            if front >= N:
                # All glasses are full, champagne is lost
                continue
            glass[front] += V
            # Cascade from front
            i = front
            while i < N and glass[i] > C[i]:
                overflow = glass[i] - C[i]
                glass[i] = C[i]
                if i + 1 < N:
                    glass[i + 1] += overflow
                # glass[i] is now full, so if i == front, advance front
                i += 1
            # Update front: all glasses from old front to i-1 are now full
            # front should be the first non-full glass
            # Since glasses before old front were already full, and we just filled front..i-1,
            # new front = i (if i < N and glass[i] <= C[i], then i is not full)
            # But we need to be careful: front was the first non-full, we filled some from front onwards
            if front < i:
                front = i  # i is either N, or glass[i] <= C[i]
        else:
            k = int(line[1]) - 1
            out.append(str(glass[k]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。