ABC190F

cosf · 2023-12-12 20:50:07 · 题解

ABC190F

首先，如果我们仅仅是求没左移时逆序对的个数，那么可以出门左转，做做 P1908。

那么，左移一位意味着什么？

相当于，原本第一位所在的所有逆序对都消失了，并且第一位放到了最后后又产生了一些新的逆序对。

这显然可以用树状数组来维护。具体就维护一个比该值大的树状数组和一个比该值小的树状数组，分别统计每个点作为逆序对前面的那一个和后面那一个的个数。

代码

#include <iostream>
using namespace std;

#define MAXN 300005
#define lowbit(x) ((x) & -(x))

#define int long long

int n;

int t1[MAXN];

void a1(int p, int v)
{
    while (p <= n)
    {
        t1[p] += v;
        p += lowbit(p);
    }
}

int q1(int p)
{
    int res = 0;
    while (p)
    {
        res += t1[p];
        p -= lowbit(p);
    }
    return res;
}

int t2[MAXN];

void a2(int p, int v)
{
    while (p <= n)
    {
        t2[p] += v;
        p += lowbit(p);
    }
}

int q2(int p)
{
    int res = 0;
    while (p)
    {
        res += t2[p];
        p -= lowbit(p);
    }
    return res;
}

int a[MAXN];

int r[MAXN];

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += q1(n - a[i]);
        a1(n - a[i], 1);
        a2(a[i] + 1, 1);
    }
    r[0] = res;
    for (int i = 1; i < n; i++)
    {
        a2(a[i] + 1, -1); // 先删再算
        a1(n - a[i], -1);
        res -= q2(a[i] + 1);
        res += q1(n - a[i]);
        a1(n - a[i], 1);
        a2(a[i] + 1, 1);
        r[i] = res;
    }
    for (int i = 0; i < n; i++)
    {
        cout << r[i] << endl;
    }
    return 0;
}