逆序对

逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 $n$，表示序列中有 $n$ 个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

样例输入

6
5 4 2 6 3 1

样例输出

11

提示

对于 $25\%$ 的数据，$n \leq 2500$。

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$。

请使用较快的输入输出。

应该不会 $O(n^2)$ 过 50 万吧 by chen_zhe。

思路

朴素法求逆序对 $O(n^2)$

两重循环遍历数组，对于每一个数，找它前面有没有严格大于自己的数，有则计一。

void solve()
{
	vector<int> v(n);
	for (auto &x : v)	cin >> x;
    int ans = 0;
    for (int i=0;i<n;i++)
        for (int j=0;j<i;j++)
            if (v[j] > v[i])
                ans ++;
    cout << ans;
}

归并排序法 (待更新…)

树状数组 $O(nlogn)$

根据逆序对的概念，对于每个数 $x$ ，每次查询区间 $[x + 1, \infty]$，求区间和，就是它前面比它大的数的个数。接着，给离散化后的点加一，后续遍历到比它小的数时，就能算上这对逆序对啦！

需要尤为注意的是：

要算的是 $[x + 1, \infty]$ 的累加和，但是树状数组的 $query(x)$ 所求是 $[1,x]$ 的累加和。因此，每次计算的贡献应为 $i - query(rnk)$ ,其中 $i$ 为当前元素下标（从0开始）。

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

void solve() 
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    
    vector<int> rank = v;
    sort(all(rank));
    rank.erase(unique(all(rank)), rank.end());
    
    vector<int> c(n + 1, 0);

    auto upd = [&](int x, int d) 
    {
        while (x <= n) 
        {
            c[x] += d;
            x += lowbit(x);
        }
    };

    auto query = [&](int x) 
    {
        int ans = 0;
        while (x > 0) 
        {
            ans += c[x];
            x -= lowbit(x);
        }
        return ans;
    };

    int ans = 0;
    for (int i=0;i<n;i++)
    {
        int rnk = distance(rank.begin(), upper_bound(all(rank), v[i]));
        ans += i - query(rnk);
        upd(rnk, 1);
    }
    cout << ans;
}

线段树 $O(nlogn)$

struct Laz
{
    int add = 0;
    void apply(const Laz &tag)
    {
        if (tag.add)
            add += tag.add;
    }
};

struct Info
{
    int sum = 0;
    Info() {}
    Info(int x) : sum(x) {}
    void apply(const Laz &tag, int len)
    {
        if (tag.add)
            sum += tag.add * len;
    }

    Info operator+ (const Info &a) const
    {
       Info res;
       res.sum = sum + a.sum;
       return res;
    }
};

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x : v) cin >> x;
    
    vector<int> rank = v;
    sort(all(rank));
    rank.erase(unique(all(rank)), rank.end());

    int ans = 0;
    SegTree<Info, Laz> seg(n);
    for (int i=0;i<n;i++)
    {
        int rnk = distance(rank.begin(), upper_bound(all(rank), v[i]));
        ans += seg.query(rnk + 1, n).sum;
        seg.modify(rnk, rnk, {1});
    }
    cout << ans;
}