https://leetcode.com/problems/count-non-decreasing-subarrays-after-k-operations/description/
题目大意
给出 $n \ (n \le 10^5)$ 长的数组 $a$，其中 $1 \le a_i \le 10^9$，给出数字 $k \ (1 \le k \le 10^9)$。问有多少子数组，可以通过不超过 $k$ 次给单个位置 $+1$ 的操作，使得该子数组单调不减。
简要题解
容易发现，对于区间 $[l, r]$，最小的增量是 $f(l, r) = \sum_{i = l}^{r} (\max_{j = l}^{i} a[j] - a[i])$。如果对于某个区间 $[l, r]$ 该增量小于 $k$，则所有 $l, r$ 的子区间也都只需要不超过 $k$ 次就可达成目标。即 $f(l, r) \le f(a, b) \ (l \le a \le b \le r)$。
证明：
$[l, r]$ 变为 $[l, r - 1]$ 因为 $f$ 中每一项都是非负的，因此去掉最后一项显然不会更大。
$[l, r]$ 变为 $[l + 1, r]$ 注意到 $\max_{j = l}^{i} \ge \max_{j = l + 1}^{i}$ 所以这也是对的。
如此，对于这个题目的 $l, r$ 的移动，假设推 $l$，则 $r$ 变化是单调的，反之推 $r$ 则 $l$ 的变化也是单调的，因此我们可能可以通过双指针解决。下面就是要解决如何在滑动的时候维护中间的值。
考虑滑左侧可能会容易一些。左侧滑动的时候，会把有边比自己小的部分全部变到和自己一样大，这是一个单调栈问题，很好维护。对应和的变化就是出栈时被增加的差值乘上段长。
右侧如果需要删掉，则减小的贡献就是这一段当前的值，减掉这个数原始的值。为了知道这一段的值，我们可以额外维护有边界对应栈上的位置的指针。当然，也可以用线段树维护所有的增量，然后这样就是多一个 log，但是好处理，好想很多。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
typedef long long LL;
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& a, int k) {
int n = a.size();
LL ans = 0;
vector<int> st;
st.push_back(n);
LL cur = 0;
int p = 1;
int j = n - 1;
for (int i = n - 1; i >= 0; i--) {
while (st.back() != n && a[st.back()] <= a[i]) {
int l = st.back();
st.pop_back();
int r = st.back() - 1;
if (r > j) {
cur += 1LL * (j - l + 1) * (a[i] - a[l]);
p = st.size();
break;
} else {
cur += 1LL * (r - l + 1) * (a[i] - a[l]);
}
}
st.push_back(i);
while (cur > k) {
cur += a[j] - a[st[p]];
j--;
if (j < st[p]) p++;
}
ans += j - i + 1;
}
return ans;
}
};
看错的题目
看成了任取区间，而不是任意一个位置。这样的话直接从差分的角度考虑，总是从加 $[p, n]$，题目更简单了。
typedef long long LL;
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& a, int k) {
int n = a.size();
LL ans = 0;
int cur = 0;
int j = 0;
for (int i = 0; i < n; i++) {
while (j + 1 < n && (a[j + 1] >= a[j] || a[j] - a[j + 1] + cur <= k)) {
cur += (a[j + 1] >= a[j] ? 0 : a[j] - a[j + 1]);
j++;
}
cout << i << ' ' << j << ' ' << cur << endl;
ans += j - i + 1;
if (i + 1 <= j && a[i] > a[i + 1]) {
cur -= a[i] - a[i + 1];
} else {
cur = 0;
j = i + 1;
}
}
return ans;
}
};