模板——树状数组求逆序对-白红宇

模板——树状数组求逆序对

阅读量：5127 次

发布时间：2019-06-13

本文共 1420 字，大约阅读时间需要 4 分钟。

题目链接：

1 #include  2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #define forn(i, n) for (int i = 0; i < (n); i++)11 #define forab(i, a, b) for (int i = (a); i <= (b); i++)12 #define forba(i, b, a) for (int i = (b); i >= (a); i--)13 #define mset(a, n) memset(a, n, sizeof(a))14 #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)15 #define P pair
               
                16 #define fi first17 #define se second18 using namespace std;19 #define N 50000520 #define maxn 100521 #define inf 0x3f3f3f3f22 #define ll long long23 ll a[N], c[N * 4];24 ll b[N];25 int n;26 int sum;27 inline int lowbit(int x) { return x & (-x); }28 void add(int x,int y)29 {30 for (; x <= N;x+=lowbit(x))31 c[x] += y;32 }33 int ask(int x)34 {35 int ans = 0;36 for (; x;x-=lowbit(x))37 ans += c[x];38 return ans;39 }40 bool cmp(int x,int y)41 {42 return b[x] > b[y];43 }44 int main()45 {46 scanf("%d", &n);47 forab(i, 1, n)48 {49 scanf("%d", b + i);50 a[i] = i;51 }52 sort(a + 1, a + 1 + n, cmp);53 // forab(i, 1, n) cout << a[i] << " ";54 // cout << endl;55 forab(i, 1, n)56 {57 58 // cout << "sum=" << sum << endl;59 add(a[i], 1);60 sum += ask(a[i] - 1);61 }62 cout << sum << endl;63 system("pause");64 }65 /*66 667 5 4 2 6 3 168 69 */