算法笔记求序列A每个元素左边比它小的数的个数(树状数组和离散化)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 
 5 using namespace std ;
 6 
 7 const int N = 100010 ;
 8 
 9 struct node{
10     int val,pos ;
11 }tmp[N];
12 int a[N] ;//离散化后的原始数组 
13 int c[N] ;//树状数组 
14 
15 
16 bool cmp(node st1,node st2){
17     return st1.val < st2.val ;
18 }
19 
20 int lowbit(int x){//取得最右边的一个1 
21     return x&(-x) ;
22 }
23 
24 int getSum(int x){//区间1~x的和 log(N) 
25     int sum = 0 ;
26     for(int i=x;i>0;i-=lowbit(i)){
27         sum += c[i] ;
28     }
29     return sum ;
30 }
31 
32 void update(int x,int v){//单点更新 log(N)
33     for(int i=x;i<=N;i+=lowbit(i)){
34         c[i] += v ;
35     }
36 }
37 
38 
39 int main(){
40     int n, x ;
41     cin >> n ;
42     
43     memset(c,0,sizeof c) ;
44     
45     for(int i=0;i<n;i++){
46         cin >> tmp[i].val ;
47         tmp[i].pos = i ;
48     }
49     
50     sort(tmp,tmp+n,cmp) ;
51     
52     for(int i=0;i<n;i++){
53         if(i==0 || tmp[i-1].val != tmp[i].val)
54             a[tmp[i].pos] = i + 1 ;//离散化 
55         else{
56             a[tmp[i].pos] = a[tmp[i-1].pos] ;
57         }
58     } 
59     
60     for(int i=0;i<n;i++){
61         update(a[i],1) ;
62         cout << getSum(a[i]-1) << endl ;
63     }
64     
65     return 0 ;
66     
67 }