题解：AT_abc413_c [ABC413C] Large Queue

__Accepted_cyx__ · 2025-12-18 21:17:12 · 题解

思路

由于 c 和 k 可达 10^9，不能逐个存储元素。
注意到添加操作是连续相同的数，可以用压缩存储：

• 用队列存储二元组 (val, cnt)。
• 插入 1 c x：直接将 (x, c) 入队。
• 删除 2 k：从队首逐个弹出整段，直到删除总数达到 k
  • 若当前段个数 \le 剩余需删除数，则整段弹出并计入总和。
  • 否则只减少该段的个数并计入部分总和。

这样每个元素最多入队出队一次，复杂度 O(Q)。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int Q;
    cin >> Q;
    queue<pair<ll, ll>> q;

    while (Q--) {
        int op;
        cin >> op;
        if (op == 1) {
            ll c, x;
            cin >> c >> x;
            q.push({x, c});
        } else {
            ll k, sum = 0;
            cin >> k;
            while (k > 0) {
                auto &[val, cnt] = q.front();
                ll take = min(k, cnt);
                sum += take * val;
                k -= take;
                cnt -= take;
                if (cnt == 0) q.pop();
            }
            cout << sum << "\n";
        }
    }

    return 0;
}