(更新点查询区间)
这题重在想到，写代码很容易了。。这题是利用线段树求逆序数，不按给定的顺序建树，而是有序地插入。比如每插入一个数，就统计之前插入的那些数里比他大的有多少个，这个数就是此时的逆序数，然后累加每个的逆序数，就是整个原始序列的逆序数，怎么统计呢？前面说了，是有序的插入，查询比它大的数岂不是查它右边就好了？即查询a[i]~n-1中插入了多少数，凡插入了的即是比他大的。这样，总的逆序数就出来了。现在求一个最小值。这里有个结论，因为每次都把第一个移到最后即可，考虑第一个元素，x[0]是此时的逆序数，把x[0]放到最后，这时要增加原来比a[0]大的个数（即n-a[0]-1个）个逆序数，同时要减少a[0]个逆序数，因为放到后面去了，前面的那些比它小的数（a[0]个）不再构成逆序数。这是即 sum = sum + n - a[i] - 1 - a[i] ，跑一边循环求最小值。。感觉自己也没说清楚，还是不懂的自己体会一下吧。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <utility> #include <cstdlib> using namespace std; #define N 5010 int tree[4*N]; int a[N]; void build(int l,int r,int rt) { tree[rt] = 0; if(l == r) { return; } int mid = (l+r)/2; build(l,mid,2*rt); build(mid+1,r,2*rt+1); } void update(int l,int r,int pos,int rt) { if(l == r) { tree[rt]++; return; } int mid = (l+r)/2; if(pos<=mid) update(l,mid,pos,2*rt); else update(mid+1,r,pos,2*rt+1); tree[rt] = tree[2*rt]+tree[2*rt+1]; } int query(int l,int r,int aa,int bb,int rt) { if(aa>r||bb<l) return 0; if(aa<=l&&bb>=r) return tree[rt]; int mid = (l+r)/2; int res = 0; if(aa<=mid) res += query(l,mid,aa,bb,2*rt); if(bb>mid) res += query(mid+1,r,aa,bb,2*rt+1); return res; } int main() { int n,i; int sum; while(scanf("%d",&n)!=EOF) { build(0,n-1,1); sum = 0; for(i=0;i<n;i++) { scanf("%d",&a[i]); sum += query(0,n-1,a[i],n-1,1); update(0,n-1,a[i],1); } int ans = 100000000; for(i=0;i<n;i++) { sum = sum+n-a[i]-1-a[i]; ans = min(ans,sum); } printf("%d ",ans); } return 0; }