提出 #74677042

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
long long n, k, a[500005], t[500005];
long long lowbit(long long x) { return x & -x; }
void update(long long x, long long v)
{
    while (x <= n)
    {
        t[x] += v;
        x += lowbit(x);
    }
}
long long query(long long x)
{
    long long res = 0;
    while (x)
    {
        res += t[x];
        x -= lowbit(x);
    }
    return res;
}
long long x, inv, ans, a1[500005], a2[500005], f[500005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (long long i = 1; i <= n; i++)
        cin >> a[i];
    for (long long l = 1; l <= n; l++)
    {
        while (x < l)
        {
            x++;
            inv += query(n) - query(a[x]);
            update(a[x], 1);
        }
        while (x < n && inv < k)
        {
            x++;
            inv += query(n) - query(a[x]);
            update(a[x], 1);
        }
        if (inv >= k)
            a1[l] = x;
        else
            a1[l] = n + 1;
        f[l] = inv;
        inv -= query(a[l] - 1);
        update(a[l], -1);
    }
    x = 0, inv = 0;
    memset(t, 0, sizeof(t));
    for (long long l = 1; l <= n; l++)
    {
        while (x < l)
        {
            x++;
            inv += query(n) - query(a[x]);
            update(a[x], 1);
        }
        while (x < n && inv < k + 1)
        {
            x++;
            inv += query(n) - query(a[x]);
            update(a[x], 1);
        }
        if (inv >= k + 1)
            a2[l] = x;
        else
            a2[l] = n + 1;
        inv -= query(a[l] - 1);
        update(a[l], -1);
    }
    for (long long l = 1; l <= n; l++)
    {
        if (f[l] == k)
            ans += a2[l] - a1[l];
    }
    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果