3420. Count Non-Decreasing Subarrays After K Operations

You are given an array nums of n integers and an integer k.

For each subarray of nums, you can apply up to k operations on it. In each operation, you increment any element of the subarray by 1.

Note that each subarray is considered independently, meaning changes made to one subarray do not persist to another.

Return the number of subarrays that you can make non-decreasing after performing at most k operations.

An array is said to be non-decreasing if each element is greater than or equal to its previous element, if it exists.

c++

class Solution {
public:
    long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
        long long res = 0, n = nums.size(), r = n - 1, now = 0;
        vector<long long> pre{0};
        for(auto& x : nums) pre.push_back(x + pre.back());
        deque<pair<int,int>> dq;
        auto query = [&](long long l, long long r) {
            return (r + 1 - l) * nums[l] - (pre[r+1] - pre[l]);
        };
        for(int i = n - 1; i >= 0; i--) {
            long long ri = i;
            while(dq.size() and nums[dq.back().first] <= nums[i]) {
                auto [l,r] = dq.back(); dq.pop_back();
                now -= query(l,r);
                ri = r;
            }
            now += query(i,ri);
            dq.push_back({i,ri});
            while(now > k) {
                now = now - nums[dq.front().first] + nums[dq.front().second];
                if(--dq.front().second < dq.front().first) dq.pop_front();
            }
            res += dq.front().second + 1 - i;
        }
        return res;
    }
};