https://atcoder.jp/contests/abc282/tasks/abc282_h
挂了好久发现二分写挂了……
对于 \(\min\{a_i\}\) 这一部分，不难想到找到当前 \(\min\{a_i\}\) 的位置计算其左右两边产生的贡献继续分为两个区间往下继续。
具体的，令当前区间为 \([l,r]\)，\(\min\{a_{l\sim r}\}=a_k\)，则分成 \([l,k-1],[k+1,r]\) 两个区间，算这两个区间对答案的贡献再继续算这两个区间内产生的贡献。
对于求贡献，选择区间数少的一个区间进行枚举，在另一个区间上进行二分求个数。
Q：为什么要选少的一个？
A：因为这样就能保证这个区间的个数不超过 \(\frac{r-l+1}{2}\) 个，能保证时间复杂度。
总时间复杂度 \(O(n\log^2 n)\)。
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 20;
long long a [N];
int p [N] [M];// st 求最小值位置
int l2 [N];
long long b [N];// b 要前缀和满足单调不降才能二分
int query (int l, int r) {
int len = r - l + 1;
int g = l2 [len];
if (a [p [l + (1 << g) - 1] [g]] < a [p [r] [g]]) {
return p [l + (1 << g) - 1] [g];
}
return p [r] [g];
}// 找到区间最小值的位置
long long s;
long long ans;
int countl (int x, int l ,int r, long long p) {
int ans = l - 1, lst = l;
while (l <= r) {
int mid = (l + r) >> 1;
if (b [mid] - b [x - 1] <= p) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return ans - lst + 1;
}
int countr (int x, int l ,int r, long long p) {
int ans = r + 1, lst = r;
while (l <= r) {
int mid = (l + r) >> 1;
if (b [x] - b [mid - 1] <= p) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
return lst - ans + 1;
}
// 分成了两个二分求解
void calc (long long l, long long r) {
if (l > r) {
return ;
}
int k = query (l, r);
int llen = k - l, rlen = r - k;
if (llen < rlen) {
for (int i = k; i >= l; -- i) {
long long t = b [k] - b [i - 1];
ans += countl (i, k, r, s - a [k]);
}
}
else {
for (int i = k; i <= r; ++ i) {
long long t = b [i] - b [k - 1];
ans += countr (i, l, k, s - a [k]);
}
}
calc (l, k - 1);
calc (k + 1, r);
// 继续往下递归
return ;
}
int main () {
int n;
scanf ("%d %lld", & n, & s);
for (int i = 3; i <= n; ++ i) {
l2 [i] = l2 [(i + 1) >> 1] + 1;
}
for (int i = 1; i <= n; ++ i) {
scanf ("%lld", & a [i]);
p [i] [0] = i;
}
for (int i = 1; (1 << i) <= n; ++ i) {
for (int j = 1 << i; j <= n; ++ j) {
if (a [p [j] [i - 1]] > a [p [j - (1 << (i - 1))] [i - 1]]) {
p [j] [i] = p [j - (1 << (i - 1))] [i - 1];
}
else {
p [j] [i] = p [j] [i - 1];
}
}
}
for (int i = 1; i <= n; ++ i) {
scanf ("%lld", & b [i]);
b [i] += b [i - 1];
}
calc (1, n);
printf ("%lld", ans);
return 0;
}