关于离散化的疑惑(?

P1908 逆序对

Zlc晨鑫 @ 2021-08-05 18:16:15

RT,这是我自己学的离散化。

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10;

int a[N], v[N], c[N], m, n;

int lowbit(int x)
{
    return x & (~x + 1);
}

// 离散化begin
void init()
{
    sort(v + 1, v + n + 1);
    m = unique(v + 1, v + n + 1) - v - 1;
}

int ask(int x)
{
    return lower_bound(v + 1, v + m + 1, x) - v;
}
// 离散化end

// 树状数组begin
void add(int x, int k)
{
    for ( ; x <= m; x += lowbit(x))
        c[x] += k;
}

int query(int x)
{
    int ans = 0;
    for ( ; x; x -= lowbit(x))
        ans += c[x];
    return ans;
}
// 树状数组end

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        v[i] = a[i];
    }
    init();
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        add(ask(a[i]), 1);
        ans += i - query((ask(a[i])));
        // 所有数的个数-小于等于x的数的个数=大于x的数的个数
    }
    printf("%lld\n", ans);
    return 0;
}

可是题解里面那种写cmp的离散化是啥啊?

这两个的复杂度一样吗qwq?


by Zlc晨鑫 @ 2021-08-05 18:17:57

所以,这两种离散化是不是不用二分的更快?


by _caiji_ @ 2021-08-05 19:30:59

两个离散化都是可行的,时间复杂度一样都是 O(n\log n)。区别在于,对于这个数列:

5
19260817 1919810 1919810 1919810 114514 

您的离散化会输出:

3 2 2 2 1

题解的离散化的一种可能输出:

5 2 3 4 1 

by Zlc晨鑫 @ 2021-08-14 14:29:54

@caijianhong 可是查询起来是不是题解的那种更快?


|