Overview

This problem involves simulating the process of pouring champagne from above into glasses arranged in a row, where overflow from one glass sequentially flows down to the glass below it. The goal is to perform this simulation efficiently.

A naive simulation would repeatedly scan glasses that are already full, making it impossible to meet the time limit. Therefore, by using Union-Find (DSU: Disjoint Set Union) to quickly detect “the next glass that is not yet full,” we can perform the simulation efficiently.

---

Analysis

Naive Approach and Its Limitations

The simplest method is to start from the 1st glass each time champagne is poured, and whenever the capacity is exceeded, add the overflow to the next level, repeating this process.

However, when a large amount of champagne is poured into a state where many glasses are already full, we end up skipping “already full glasses” one by one each time. In the worst case, a single pouring operation takes \(O(N)\) time, and with \(Q\) queries, the total time complexity becomes \(O(NQ)\). Since \(N, Q \le 2 \times 10^5\), this will result in a Time Limit Exceeded (TLE) verdict.

Key to Optimization: Jumping to “the Next Non-Full Glass”

For optimization, we consider a method to “quickly skip glasses that are already full.”

When glass \(i\) becomes full, the next time champagne flows into glass \(i\), it should immediately flow to “the nearest glass below glass \(i\) that is not yet full.”

For managing such “representatives of groups (in this case, the nearest glass with available capacity),” Union-Find (DSU) is ideal.

Specifically, we manage it as follows: - The moment glass \(i\) becomes full, we connect (unite) glass \(i\) and glass \(i+1\). - When connecting, we always merge so that the one with the larger index (the lower glass) becomes the root (representative).

By doing this, when champagne is poured into (or flows into) glass \(i\), simply calling find(i) on the DSU allows us to identify “the glass with the smallest index that is not yet full and should receive the champagne next” in nearly \(O(1)\) time.

---

Algorithm

1. DSU Initialization

Prepare a DSU of size \(N + 2\). - Elements from \(1\) to \(N\) correspond to each glass. - \(N + 1\) represents a sentinel for “the bottom of the tower (the ground).” It serves the role of catching champagne that overflows from the lowest glass, with infinite capacity (or simply a place to discard overflow). - In the initial state, since no glass is full, each one is the root of its own independent set.

2. Processing Operation \(1\) (Pouring)

When an instruction to pour \(V\) milliliters of champagne into the 1st glass arrives, repeat the following steps:

1. Obtain the index of the glass that champagne should currently flow into with curr = dsu.find(1).
2. While curr <= n and \(V > 0\), execute the following:
   • Calculate the current remaining capacity of glass curr: space = C[curr] - A[curr].
   • Case A: When \(V \ge \text{space}\) (the glass becomes full)
     • Glass curr becomes full.
     • Subtract space from \(V\) (update the remaining champagne amount), and set A[curr] = C[curr].
     • Since glass curr is now full, perform dsu.unite(curr, curr + 1) to connect the path to the next glass.
     • Update the next glass to pour into with curr = dsu.find(curr).
   • Case B: When \(V < \text{space}\) (the glass does not become full)
     • All \(V\) can be poured into glass curr.
     • Add \(V\) to A[curr], and set \(V = 0\).
     • Exit the loop.

3. Processing Operation \(2\) (Query)

Output the current amount A[k] in glass \(k\) as is.

---

Complexity

Time Complexity: \(O((N + Q) \alpha(N))\)

• The event of “a glass becoming full” occurs at most \(N\) times across the entire tower.
• Since dsu.unite is called only when a glass becomes full, the total number of unite executions is at most \(N\).
• Therefore, the total number of iterations of the while loop in operation \(1\) is bounded by at most \(N + Q\) across all queries.
• Each DSU operation (find, unite) can be performed in \(O(\alpha(N))\) (nearly constant time) using the inverse Ackermann function \(\alpha\), so the overall time complexity is \(O((N + Q) \alpha(N))\), which runs extremely fast.

Space Complexity: \(O(N)\)

• \(O(N)\) memory is used for the glass capacity array C, the current champagne amount array A, and the array managing the DSU’s parent nodes.

---

Implementation Notes

• Forcing the merge direction in DSU: In a typical DSU, “union by size” or similar techniques are used to keep the tree height low, but in this problem, “the one with the larger index must always become the parent.” In the unite function, implement it so that when root_i < root_j, we always set parent[root_i] = root_j.

• Sentinel at index \(N+1\): When the lowest glass (at level \(N\)) becomes full, it is merged with \(N+1\) below it. To prevent out-of-bounds array access, the DSU size must be allocated as \(N+2\).

• Fast I/O: Since the number of queries is large, in C++ it is recommended to use fast std::cin (ios_base::sync_with_stdio(false); cin.tie(NULL);) and to use "\n" instead of std::endl (which causes a buffer flush) when outputting newlines.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.