B. Infinity Card Decks

题目描述

有 \(N\) 张牌，第 \(i\) 张牌打出需要 \(A_i\) 能量，获得 \(B_i\) 能量。一开始你有 \(M\) 的能量。

如果一些牌，无论怎么无限的按照随机顺序打出，都不会缺少能量，则我们称这是一个无限牌组。

求有多少个子区间是无限牌组。

思路

很容易想到，一个无限牌组必须满足以下条件。

1. \(\sum A_i \le \sum B_i\)，因为如果不满足该条件，那么每经过一轮能量就会减少，所以最终一定会不够。
2. 在第一轮打出时不可能缺少能量。因为满足条件 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;
}