【51nod 3121】【树状数组】（求逆序对）小陶与杠铃片

【51nod 3121】【树状数组】（求逆序对）小陶与杠铃片

小陶与杠铃片

题目解题思路Code

51nod 3121 小陶与杠铃片

---

题目

输入样例

10
16808 75250 50074 143659 108931 11273 27545 50879 177924 37710

输出样例

20

---

解题思路

本质就是找逆序对
把逆序对全部对调，就一定能顺序，也就是至少次数

逆序对暴力方法，统计有多少个比自己大的排在前面
n ^ 2 肯定是会T的

4 1 3 2
将所有的数从小到大排序，并且保留原位置标号
num：1 2 3 4
id：    . .   . 2 4 3 1

（1，2）在1前比1小的个数为0；1排在了2，所以一定有一个数(4)与1构成逆序对，ans += 1；在 2 的位置插入1
（2，4）4位置上有1了，也就是在2前比2小的数有1个；2排在4，有两个数（3，4）与2构成逆序对，ans += 4；在4插入1
以此类推（可以在上图标记一下推导）

num：1 2 3 4
id：    . .   . 2 4 3 1
ans ：1 2 1 0
加起来就是答案

原理：因为num已经排过序了，所以插入过的数都≤当前数
又是按照id来查询的，所以每查询一个数，返回值就是在id之前还比num小的个数，也就是能与num组成逆序对的个数

---

Code

#include 
#define N 500000
#define ll long long

using namespace std;

pair a[N + 100];
ll n, m, x, y, c, t[N + 200], ans;

ll lowbit(ll x) { return (x & -x); }

void add(ll x, ll y) {
	for(; x <= n; x += lowbit(x)) t[x] += y;
}

ll sum(ll x) {
	ll ans = 0;
	for(; x; x -= lowbit(x)) ans += t[x];
	return ans;
}

int main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%lld", &a[i].first);
		a[i].second = i;
	}
	sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i ++) {
		ans += a[i].second - sum(a[i].second - 1) - 1;
		add(a[i].second, 1);
	}
	printf("%lld", ans);
}