题目链接：hdu1394
思路：
先用线段树求出原始序列的逆序对数。
序列中的n个数的范围是0~n-1，这点需要注意，根据这点可以很快速的求出改变后的序列的逆序对数。把位于第一位的num[i]移到最后一位，则变化的逆序对数是在上一个序列（即num[i]为第一位的序列）的基础上加上比num[i]大的数的个数，再减去比num[i]小的数的个数（因为num[i]移到最后以后，只能与前面比他大的数构成逆序对，而在上一个序列中与num[i]构成逆序对的在此序列则没办法构成）。
#include#include using namespace std; #define N 5005 int n,flag; struct node { int left,right; int num; }s[N<<2]; int num[N]; void build(int left,int right,int n) { s[n].left = left; s[n].right = right; s[n].num = 0; if(left == right) return ; int mid = (left + right) >> 1; build(left, mid, n<<1); build(mid+1, right, n<<1|1); } void update(int left,int right,int n) { if(s[n].left == s[n].right) { s[n].num++; return; } int mid = (s[n].left + s[n].right) >> 1; if(left > mid) update(left, right, n <<1|1);//右子树 else if(right <= mid) update(left, right, n << 1);//左子树 s[n].num = s[n<<1].num + s[n<<1|1].num; } int query(int left,int right,int n) { if(s[n].left == left && s[n].right == right) { return s[n].num; } int mid = (s[n].left + s[n].right) >> 1; if(right <= mid) return query(left, right, n<<1); else if(left > mid) return query(left, right, n<<1|1); else return query(left, mid, n<<1)+query(mid+1, right, n<<1|1); } int main() { int m,i; while(~scanf("%d",&m)) { build(1,m,1); int sum = 0; for(i = 1; i <= m; i ++) { scanf("%d",&num[i]); sum += query(num[i]+1,m,1);//num[i]+1是要排除零 update(num[i]+1,num[i]+1,1); } int ans = sum; for(i = 1; i <= m; i ++) { sum = sum + (m - (num[i]+1)) - num[i]; //上一个序列的逆序对数加上比num[i]大的（num[i]放到最后一个位置后，能与前面每一个比它大的构成逆序对）再减去比num[i]小的 ans = min(sum,ans); } printf("%d\n",ans); } return 0; }