Let \(f(k)\) be the number of pairs \((l,r)\) such that the inversion number of \((P _ l,P _ {l+1},\ldots,P _ r)\) is at most \(k\). What we want to find is \(f(k)-f(k-1)\), so it is sufficient to evaluate \(f\) fast enough for given \(P\) and \(K\).

When the inversion number of \((P _ l,P _ {l+1},\ldots,P _ r)\) is \(X\), the inversion number of \((P _ {l+1},P _ {l+2},\ldots,P _ r)\) equals \(X-\bigl(\)the number of indices \(i=l+1,l+2\ldots,r\) such that \(P _ l\gt P _ i\bigr)\). Also, when the inversion number of \((P _ l,P _ {l+1},\ldots,P _ r)\) is \(X\), the inversion number of \((P _ l,P _ {l+1},\ldots,P _ {r-1})\) is \(X-\bigl(\)the number of indices \(i=l,l+1\ldots,r-1\) such that \(P _ r\lt P _ i\bigr)\).

Hence, when the inversion number of \((P _ l,P _ {l+1},\ldots,P _ r)\) is \(k\) or less, then the inversion numbers of \((P _ {l+1},P _ {l+2},\ldots,P _ r)\) and \((P _ l,P _ {l+1},\ldots,P _ {r-1})\) are also \(K\). This property allows us to use the sliding window trick to find, for each \(l\), the maximum \(r\) satisfying the condition.

The following is sample code:

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/fenwicktree>

int main() {
    using namespace std;
    unsigned N;
    unsigned long K;
    cin >> N >> K;
    vector<unsigned> P(N);
    for (auto&& p : P) {
        cin >> p;
        --p;
    }

    // Function that finds f(K)
    const auto solve{[N, &P](unsigned long K) {
        atcoder::fenwick_tree<unsigned> bit(N); // Supports element update and segment sum
        unsigned long now{}; // Current inversion number
        unsigned long ans{}; // The number of conforming segments
        for (unsigned l{}, r{}; l < N; ++l) { // Sliding window
            if (r < l) r = l; // If empty, advance r too
            while (r < N && now + bit.sum(P[r], N) <= K) { // While adding r does not make the inversion number greater than K
                now += bit.sum(P[r], N); // append r
                bit.add(P[r], 1);
                ++r;
            }
            ans += r - l; // There are (r - l) segments whose left end is `l`
            now -= bit.sum(0, P[l]); // remove `l`
            bit.add(P[l], -1);
        }
        return ans;
    }};

    cout << solve(K) - (K ? solve(K - 1) : 0) << endl; // f(K) - f(K - 1) が答え
    return 0;
}