有一个空序列，需要维护如下三个操作：
1 x：在序列中添加 \(x\)。2 x：把序列中每个元素的值减去 \(x\)。3：重复从第一条到本条操作的前一条的所有操作，包括操作 \(3\)。
当一个数的值 \(\leq 0\) 时，它将被移出序列。求最后有多少个数还在序列中。答案对 \(998244353\) 取模。
\(n \leq 8\times10^5\)，\(x\leq 10^9\)。
趣味题。我们分别考虑每次 \(1\) 操作新增的猪对答案的贡献。考虑 \(3\) 操作的实质：设之前造成的伤害值总和为 \(k\)，那么对于一只猪 \(x\)，它会变成一只 \(x\) 和一只 \(x-k\)。对于 \(k=0\) 的情况我们特殊处理，那么由于每次 \(3\) 操作后 \(k\) 的值至少 \(\times 2\)，所以对于任意一只猪，其之后有意义的 \(3\) 操作至多只有 \(\mathcal{O}(\log V)\) 个。
\(2\) 操作之间显然可以任意交换顺序。倒着做，提前减掉后面的 \(2\) 操作，就变成一个这样的问题：有 \(\mathcal{O}(\log V)\) 个数 \(k_i\)，每个数选或不选，问选出来的数总和小于 \(x'\) 的方案数。这是一个背包问题，但由于可以通过排序使得 \(k_i \geq k_{i+1} \times 2\)，因此存在更优的做法：从大到小枚举 \(k_i\)，若当前 \(k_i \geq x'\)，那么一定不选。当 \(k_i < x\) 时，如果不选，那么之后的元素的和一定不超过 \(k_i\)，因此可以随便选，否则令 \(x' \gets x'-k_i\) 并考虑下一个元素即可。总时间复杂度 \(\mathcal{O}(n \log V)\)。
code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 8e5 + 5, mod = 998244353, inf = 1e9;
int n, m, a[N], b[N], c[N], cnt, pw2[N];
signed main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
pw2[0] = 1;
for (int i = 1; i <= n; i++) pw2[i] = 1LL * pw2[i - 1] * 2 % mod;
int lim = inf, sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 1 || a[i] == 2) cin >> b[i];
if (a[i] == 2) sum += b[i];
sum = min(sum, lim);
if (a[i] == 3) b[i] = sum, sum = sum * 2;
sum = min(sum, lim);
}
sum = 0;
int coef = 1, ans = 0;
for (int i = n; i >= 1; i--) {
if (a[i] == 2) sum += b[i], sum = min(sum, lim);
else if (a[i] == 3) {
if (b[i] == lim) continue;
if (b[i] == 0) { coef = 1LL * coef * 2 % mod; continue; }
c[++cnt] = b[i];
} else {
b[i] -= sum;
if (b[i] <= 0) continue;
int f = 0, t = b[i];
for (int j = 1; j <= cnt; j++) if (t > c[j]) {
f = (f + pw2[cnt - j]) % mod;
t -= c[j];
}
f = (f + 1) % mod;
ans = (ans + 1LL * coef * f % mod) % mod;
}
}
cout << ans << "\n";
return 0;
}