深圳网络营销推广_江西邢台网络科技_seo排名优化方式方法_做整站优化

                                1282: 【J1】求逆序对

                                        时间限制: 1 Sec  内存限制: 128 MB
                                                        提交: 2  解决: 164
                                                [提交][状态][命题人:xuting]

题目描述

给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。

输入

第一行，一个数 n，表示序列中有 n个数。

第二行 n 个数，表示给定的序列。序列中每个数字不超过 109。

输出

输出序列中逆序对的数目。

样例输入

4
3 2 3 2

样例输出

3

提示

数据规模

对于所有数据，1<n≤5×105

代码敬上：

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N = 5e6 + 10;
int tr[N * 2], n,ans;
int lowbit(int x) {return x & (-x);
}
void add(int x, int v) {while (x <= n) {tr[x] += v;x += lowbit(x);}
} 
int sum(int x) {int ans = 0;while (x) {ans += tr[x];x -= lowbit(x);}return ans;
} 
int main() {cin >> n;for (int i = 1; i <= n; i++) {int v;cin >> v;add(v, 1);ans += i - sum(v);}cout << ans << endl;return 0;
}