題目大意

有一個初始為空的序列 $A$，$Q$ 次操作分為兩類：

• 第一類：將 $c$ 個 $x$ 放到 $A$ 的末尾。
• 第二類：將前 $k$ 個數的和輸出并移除它們。

思路

這是一個求和問題，想到的第一個思路是前綴和。但是前綴和的維護需要使用樹狀數組，不僅麻煩還費時間、空間，在一道 $\text{300pts}$ 的 C 題中顯然不現實。

既然不能完美地算出這個和，我們考慮一個稍微暴力的做法。如果我們直接按照題意去維護序列，空間會炸掉（因為 $c$ 最大是 $10^9$），于是想到只記下每一個“塊”。在這里，我們定義“塊”為在每次第一類操作中添加的 $c$ 個 $x$ 組成的子段。因為最多有 $Q$ 次操作，所以空間是沒問題的。我們使用一個滑動窗口去維護，$l$ 表示目前沒有被刪除的塊中編號最小的一個的編號，$r$ 表示目前存在的塊中編號最大的一個的編號，$va{l}_i$ 表示編號為 $i$ 的塊的值，$nu{m}_i$ 表示編號為 $i$ 的塊還有多少個數沒被刪除。

于是，對于第一類操作，我們可以直接 $O(1)$ 添加：

x 和 c 為輸入的值
val[++r] = x;
num[r] = c;

對于第二類操作，我們就需要花費一些時間去查找了，從 $l$ 開始依次遍歷每一個塊 $i$，刪掉 $\min (nu{m}_i,k_{剩余})$ 個數，直到 $k_{剩余}$ 為零，在刪的過程中順便求和：

while (k > 0)
{答案 += min(num[l], k) * val[l]if (能完整的刪完這一個塊)k -= num[l], l++else num[l] -= k
}

代碼

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int q, l = 1, r; // l 的初始值為 1 不要忘記
int val[200010];
int num[200010];int main()
{cin >> q;while (q--){int op;cin >> op;if (op == 1){int c, x;cin >> c >> x;val[++r] = x;num[r] = c;}else{int k;cin >> k;long long ans = 0; // 不要忘記開 long longwhile (k > 0){ans += 1LL * min(num[l], k) * val[l];if (k >= num[l]) k -= num[l], l++;else num[l] -= k, k = 0;}cout << ans << endl;}}return 0;
}

總結

時間復雜度……不太會算，通過本題是沒有問題的。如果您能計算這份代碼的時間復雜度，歡迎在評論區中提出！