前置题目：石头剪刀布大赛
很经典的问题，可以参考一个比这个简单容易想的 *2500 的做法。
先想判定条件再考虑怎么计数。
因为少写了一个 case 导致 Au \(\to\) Ag，有点难评。
不难想到记录 \(c_i = b_i - a_i\)。
我们考虑怎样才能无限下去：
- 卡牌打完之后的费用变化是正的，不然会一直变小，那么就是 \(\sum c_i \geq 0\)
考虑安排一张卡使得其付不出那么多的费用。
-
考虑全部先排负的，然后放一张正的 \(a_i\) 的最大的，形式化后就是 \(E + \sum \min\{c_i, 0\} < a_i (c_i > 0)\)
-
考虑全部排负的中抽出一张卡使得其付不起，那么就是：\(E + \sum\min\{c_i, 0\} - c_i < a_i (c_i < 0)\) 我们考虑移项，那么就是 \(E + \sum\min\{c_i, 0\} < b_i (c_i < 0)\)
不难发现这个就是所有的选择 hack 掉区间的方法，因为如果可以通过这三种手上的钱是会一直加的，所以更 hack 不掉了。
不难发现 \(\sum \min\{c_i, 0\}\) 单调递减，满足条件的 \(a_i\) 和 \(b_i\) 单调递增，所以区间左端点对应的最大合法区间右端点具有单调性。我们可以双指针，也可以ST表二分来解决问题。
最后相当于数 \([l, r]\) 中 \(sum_i \geq k\) 的个数，普通二维数点即可。
复杂度线性对数。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
using namespace std;
typedef long long ll;
const int _ = 1e6 + 5;
int n, tn;
ll E;
int a[_], b[_], c[_], lg[_];
ll sum[_], sumd[_], tmp[_];
int st[_][21][2];
vector <pair<int, int> > qv[_];
ll ans = 0;
int tr[_];
void add (int x, int k) {
for ( ; x <= tn; x += x & -x) tr[x] += k;
}
int query (int x) {
int ret = 0;
while(x) ret += tr[x], x -= x & -x;
return ret;
}
/*
e + sc < mxa
e + sc < bi
e + sc - ci < ai
*/
int querymx (int l, int r, int id) {
int k = lg[r - l + 1];
return max(st[l][k][id], st[r - (1 << k) + 1][k][id]);
}
bool check (int l, int r) {
ll d = E + sumd[r] - sumd[l - 1];
// cout << d << " " << l << " " << r << endl;
if (d < querymx(l, r, 0) || d < querymx(l, r, 1)) return false;
return true;
}
int main () {
cin >> n >> E;
lg[0] = -1, tmp[++ tn] = 0;
rep(i, 1, n) lg[i] = lg[i >> 1] + 1, scanf("%d", & a[i]);
rep(i, 1, n) {
scanf("%d", & b[i]);
c[i] = b[i] - a[i], sum[i] = sum[i - 1] + c[i];
tmp[++ tn] = sum[i], sumd[i] = sumd[i - 1];
if (c[i] < 0) {
sumd[i] += c[i], st[i][0][1] = b[i];
} else st[i][0][0] = a[i];
}
sort(tmp + 1, tmp + 1 + tn),
tn = unique(tmp + 1, tmp + 1 + tn) - (tmp + 1);
rep(i, 0, n) sum[i] = lower_bound(tmp + 1, tmp + 1 + tn, sum[i]) - tmp;
rep(k, 1, 20)
rep(i, 1, n - (1 << k) + 1) rep(t, 0, 1)
st[i][k][t] = max(st[i][k - 1][t], st[i + (1 << k - 1)][k - 1][t]);
rep(i, 1, n) {
int l = i, r = n, retp = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(i, mid)) l = mid + 1, retp = mid;
else r = mid - 1;
}
if (retp) {
qv[retp].push_back({sum[i - 1], 1});
qv[i - 1].push_back({sum[i - 1], -1});
}
}
rep(i, 1, n) {
add(sum[i], 1);
for (auto v : qv[i]) {
int val = v.first, coef = v.second;
ans += 1ll * (query(tn) - query(val - 1)) * coef;
}
}
cout << ans;
return 0;
}