AtCoder AT_abc413_c [ABC413C] Large Queue 题解

题目大意

有一个初始为空的序列 $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;
}

总结

时间复杂度……不太会算，通过本题是没有问题的。如果您能计算这份代码的时间复杂度，欢迎在评论区中提出！