http://acm.hdu.edu.cn/showproblem.php?pid=1394
每读一个数,先查询前面有多少比它大的数(在代码中我们是查询[x,n-1]范围内的数),然后将位置x的数+1
把第一个数在序列末尾时,因为比x小的数(0~x-1)都在x前面了,所以逆序对数减少了x;因为比x大的数(x+1~n-1)都在x前面了,所以逆序对数增加了n-1-x。这样每次移动,逆序对数 += n-1-2*x
完整代码:
/*78ms,320KB*/ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define root 0, n, 1 const int mx = 5000; int sum[mx << 2], x[mx]; inline void pushup(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void update(int p, int addval, int l, int r, int rt) { if (l == r) { sum[rt] += addval; return; } int m = (l + r) >> 1; if (p <= m) update(p, addval, lson); else update(p, addval, rson); pushup(rt); } int query(int ql, int qr, int l, int r, int rt) { if (ql <= l && r <= qr) { return sum[rt]; } int sum = 0, m = (l + r) >> 1; if (ql <= m) sum += query(ql, qr, lson); if (m < qr) sum += query(ql, qr, rson); return sum; } int main() { int n, i, inver, minans; while (~scanf("%d", &n)) { memset(sum, 0, sizeof(sum)); --n; inver = 0; for (i = 0; i <= n; ++i) { scanf("%d", &x[i]); inver += query(x[i], n, root); update(x[i], 1, root); x[i] <<= 1; } minans = inver; for (i = 0; i <= n; ++i) { inver += n - x[i]; minans = min(minans, inver); } printf("%d\n", minans); } return 0; }
HDU 1394 Minimum Inversion Number (最小逆序对数&RMQ线段树)
原文:http://blog.csdn.net/synapse7/article/details/19411963