B. Infinity Card Decks
题目描述
有 \(N\) 张牌，第 \(i\) 张牌打出需要 \(A_i\) 能量，获得 \(B_i\) 能量。一开始你有 \(M\) 的能量。
如果一些牌，无论怎么无限的按照随机顺序打出，都不会缺少能量，则我们称这是一个无限牌组。
求有多少个子区间是无限牌组。
思路
很容易想到，一个无限牌组必须满足以下条件。
- \(\sum A_i \le \sum B_i\)，因为如果不满足该条件，那么每经过一轮能量就会减少，所以最终一定会不够。
- 在第一轮打出时不可能缺少能量。因为满足条件 1，所以能量每过一轮都是单调不降的，所以第一轮的能量是最少的。
我们先来看条件 2：
- 我们要枚举一张牌 \(i\)，使得在出这张牌的时候能量不足。在这之前，肯定会把其他 \(A_j>B_j且i\ne j\) 的 \(j\) 出掉。
- 如果 \(A_i\le B_i\)，那么此时要满足 \(M\ge A_i+\sum \max(0,A_j-B_j)\)。
- 否则如果 \(A_i>B_i\)，那么此时要满足 \(M\ge A_i+(\sum \max(0,A_j-B_j)-(A_i-B_j))=B_i+\sum \max(0,A_j-B_j)\)。
- 上面两式合起来就是 \(M\ge \min (A_i,B_i)+\sum \max(0,A_j-B_j)\)。
所以一个区间 \([l,r]\) 要满足 \(M\ge \max\limits_{i=l}^r\{\min (A_i,B_i)\}+\sum \limits_{i=l}^r \max(0,A_i-B_i)\)。这个使用双指针求解。
接着我们考虑满足条件 1，我们可以做一个 \(A_i-B_i\) 的前缀和，离散化后用树状数组统计数量即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 1000005;int n, m, a[MAXN], b[MAXN], log_2[MAXN];
ll ans, st[21][MAXN], pre[MAXN], tr[MAXN];
vector<ll> X;int Getmax(int l, int r) {return max(st[log_2[r - l + 1]][l], st[log_2[r - l + 1]][r - (1 << log_2[r - l + 1]) + 1]);
}int lowbit(int x) {return x & -x;
}void update(int p, ll x) {for(; p <= n + 1; tr[p] += x, p += lowbit(p)) {}
}ll Getsum(int p) {ll sum = 0;for(; p; sum += tr[p], p -= lowbit(p)) {}return sum;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) {cin >> a[i];}for(int i = 1; i <= n; ++i) {cin >> b[i];pre[i] = pre[i - 1] + a[i] - b[i];X.emplace_back(pre[i]);st[0][i] = min(a[i], b[i]);}X.emplace_back(0);sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());for(int i = 0; i <= n; ++i) {pre[i] = lower_bound(X.begin(), X.end(), pre[i]) - X.begin() + 1;}for(int i = 1; i <= 20; ++i) {for(int j = 1; j <= n; ++j) {if(j + (1 << i) - 1 <= n) {st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);}}}for(int i = 2; i <= n; ++i) {log_2[i] = log_2[i / 2] + 1;}ll sum = 0;for(int i = 1, j = 1; i <= n; sum -= max(0, a[i] - b[i]), update(pre[i], -1), ++i) {for(; j <= n && Getmax(i, j) + sum + max(0, a[j] - b[j]) <= m; sum += max(0, a[j] - b[j]), update(pre[j], 1), ++j) {}ans += Getsum(pre[i - 1]);if(j == i) {sum += max(0, a[j] - b[j]), update(pre[j], 1), ++j;}}cout << ans;return 0;
}
