树状数组—（离散化）求比较大的数逆序数的个数

//树状数组大范围求逆序数的离散化模板    --cyl 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int discrete[N],s[N];    //离散数组 
struct node
{
    long long  x;
    int num;    //下标 
}T[N]; 
bool cmp(node s1,node s2){
    return s1.x <s2.x;
}
int lowbit(int x){
    return x&(-x);
}
int sum(int x)  //求出现在x这个位置前边的和 这个求出是顺序的 
{
    int ans=0;
    while(x){
        ans+=s[x];
        x-=lowbit(x); 
    }
    return ans;
}
void insert(int x) //离散化后的数组更新 
{
    while(x<=n){
        s[x]++;
        x+=lowbit(x); 
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(s,0,sizeof(s));
        for(int i=1;i<=n;i++){
            scanf("%lld",&T[i].x);
            T[i].num=i;
        }
        sort(T+1,T+1+n,cmp);
        for(int i=1;i<=n;i++)
            discrete[T[i].num]=i;       //离散化后的坐标 
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            insert(discrete[i]);        //第i次输入后的位置 
            ans+=(i-sum(discrete[i]));  //所有的逆序数之和 
        } 
        printf("%d\n",ans); 
    } 
} 
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
 

文章来源: englishcode.blog.csdn.net，作者：知识浅谈，版权归原作者所有，如需转载，请联系作者。

原文链接：englishcode.blog.csdn.net/article/details/78586206