\(f(k)\) を \((P _ l,P _ {l+1},\ldots,P _ r)\) の転倒数が \(k\) 以下であるような \((l,r)\) の個数と定めます。 求めるものは \(f(k)-f(k-1)\) なので、\(P\) および \(k\) が与えられたときに \(f\) を十分高速に求められればよいです。

\((P _ l,P _ {l+1},\ldots,P _ r)\) の転倒数が \(X\) であるとき、\((P _ {l+1},P _ {l+2},\ldots,P _ r)\) の転倒数は \(X-\bigl(P _ l\gt P _ i\) なる \(i=l+1,l+2\ldots,r\) の個数\(\bigr)\) になります。 また、\((P _ l,P _ {l+1},\ldots,P _ r)\) の転倒数が \(X\) であるとき、\((P _ l,P _ {l+1},\ldots,P _ {r-1})\) の転倒数は \(X-\bigl(P _ r\lt P _ i\) なる \(i=l,l+1\ldots,r-1\) の個数\(\bigr)\) になります。

よって、\((P _ l,P _ {l+1},\ldots,P _ r)\) の転倒数が \(k\) 以下であるとき、\((P _ {l+1},P _ {l+2},\ldots,P _ r)\) や \((P _ l,P _ {l+1},\ldots,P _ {r-1})\) の転倒数も \(k\) 以下になります。 このことから、上の関係を使って計算することで尺取り法を用いて各 \(l\) に対する条件を満たす \(r\) の最大値を高速に求めることができます。

実装例は以下のようになります。

#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;
    }

    // f(K) を求める関数
    const auto solve{[N, &P](unsigned long K) {
        atcoder::fenwick_tree<unsigned> bit(N); // 一点更新区間和を求める
        unsigned long now{}; // 現在の転倒数
        unsigned long ans{}; // 条件を満たす区間の総数
        for (unsigned l{}, r{}; l < N; ++l) { // 尺取り法を行う
            if (r < l) r = l; // 空なら i と同時に進めておく
            while (r < N && now + bit.sum(P[r], N) <= K) { // 追加しても転倒数が K を越えないなら
                now += bit.sum(P[r], N); // r を追加する
                bit.add(P[r], 1);
                ++r;
            }
            ans += r - l; // 左端が l である条件を満たす区間は r - l 個
            now -= bit.sum(0, P[l]); // l を外す
            bit.add(P[l], -1);
        }
        return ans;
    }};

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