POJ 2299 树状数组求逆序对

题意

给定一组序列可转换相邻项的序列， 求让它排成非递减的最小操作数

---

题解

就是求序列逆序对数， 但是序列最大数据较大， 数组开不出来， 所以需要现进行离散化 比如 9， 1， 0， 5， 4 ->0, 1, 4, 5, 9初始序列在排序后序列下标为5， 2， 1， 4， 3 就是把上限较大的元素集离散成500000数据量内的可执行的可求逆序对下表序列， 这样离散后元素最大为500000， 用树状数组或者线段树都可以求解

---

离散化操作

先定义结构体，并重载’<’

struct node{ int idx, v; bool operator < (const node& rhs){ return v < rhs.v; } }

离散化时， 每个给定元素下标， 然后排序， 排序后用一个数组记录原先元素排序后的位置

---

树状数组求逆序对

一个个插入到树状数组中， 每插入一个数， 统计比他小的数的个数

AC code:

#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define lowbit(x) (x & (-x)) #define LL long long #define debug 0 const int maxn(500005); LL sum[maxn], c[maxn]; int n; struct node { int idx, v; bool operator < (const node& rhs) { return v < rhs.v; } }a[maxn]; void add(int id, int v) { while (id <= n) { c[id] += v; id += lowbit(id); } } int getSum(int id) { int res = 0; while (id) { res +=c[id]; id -= lowbit(id); } return res; } int main() { #if debug freopen("in.txt", "r", stdin); #endif //debug while (cin >> n, n) { for (int i = 1; i <= n; ++i) { cin >> a[i].v; a[i].idx = i; } sort(a + 1, a + n + 1); for (int i = 1; i <= n; ++i) sum[a[i].idx] = i; LL ans = 0; memset(c, 0, sizeof(c)); for (int i = 1; i <= n; i++) { add(sum[i], 1); ans += i - getSum(sum[i]); } cout << ans << endl; } return 0; }