P1908 逆序对

题目链接：P1908 逆序对

离散化：

• 离散化（Discretization），把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。（转自网络）

  个人理解：

• 对于一些数据，我们不需要知道它本身值的大小，而需要这些数据互相对应的位置，那么采用离散化进行数据处理。
• 而逆序对正好符合这一特点，例如(2000,100,300000)可以转换为(2,1,3)

离散化代码如下：

bool cmp(Node a,Node b){
    if(a.value != b.value) return a.value < b.value;
    return a.point < b.point;
}
n = read();
for(int i = 1; i <= n; i ++ ){
        node[i].value = read();
        node[i].point = i;
}
sort(node + 1, node + n + 1,cmp);
for(int i = 1; i <= n; i ++ ){
    b[node[i].point] = i;
}

• Q1：怎么统计第 i 个数会与第1~ i−1个数构成多少个逆序对呢?
  考虑根据值来建树状数组 , 初始树状数组为全 0。现在按照序列从左到右将数据的值对应的位置的数加一，代表又有一个数出现，因此，循环到第i项的时候，前面i-1项已经加入到树状数组中，那么逆序对的数量为总个数i- 它前面所有比它小的个数(前缀和sum(x))，即i - sum(x);
• Q2:用a[i]来建立树状数组，空间不够用怎么办?
  这启发我们对数据离散化，先将数据排序，再用 1 ~ n分别对应 n 个数表示它们的相对大小，对新的序列建树状数组空间就够了

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 5e5 + 10;

int read(){
    char x = getchar();
    int ans = 0;
    for(;x < '0' || x >'9' ; x = getchar());
    for(;x >= '0' && x <= '9' ; x = getchar()){
        ans *= 10;
        ans += (x - '0');
    }
    return ans;
}

struct Node{
    int value,point;
}node[N];

int n;
int b[N],tr[N];

void add(int x,int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x){
    int ans = 0;
    for(int i = x; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}

bool cmp(Node a,Node b){
    if(a.value != b.value) return a.value < b.value;
    return a.point < b.point;
}

int main() {
    n = read();
    for(int i = 1; i <= n; i ++ ){
        node[i].value = read();
        node[i].point = i;
    }
    sort(node + 1, node + n + 1,cmp);
    for(int i = 1; i <= n; i ++ ){
        b[node[i].point] = i;
    }
    ll ans = 0;
    for(int i = 1; i <= n; i ++ ){
        add(b[i],1);
        ans += i - sum(b[i]);
    }    
    cout<<ans;
    return 0;
}

感谢学无止境大佬提供的思路