n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。 每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。 如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。 请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。 如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入的第一行包含一个整数n，表示小朋友的个数。 第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
3 3 2 1
9
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
对于10%的数据， 1<=n<=10； 对于30%的数据， 1<=n<=1000； 对于50%的数据， 1<=n<=10000；
对于100%的数据，1<=n<=100000，0<=Hi<=1000000。
这题真是搞死我了，开始老是往冒泡排序上面想，因为排序常用熟悉买，发现不能解决不高兴程度最小的问题。
后来想到了逆序数（这个读者可以自己百度一下），最先想的当然是暴力，看看数据范围后我果断放弃了。想到了树状数组（读者可以自己百度）。下面我来详细分析一下。
我们以3 2 1为例吧！
第一次读入3，此时读入的数据量为1个，变成这样
C[1] C[2] C[3] C[4] C[5] C[6] C[7] C[8]
0 0 0 1 0 0 0 0
可以看到sum(C[1],C[4])=1(可以由树状数组的统计数组得到)，这个是小于等于3的数字的个数，也就是说当输入第一个数字3的时候没有比它小的数字存在，这时我们用 输入数字总数-sum(C[1],C[4])=0，也就是说大于3的数字的个数为0，我们令b[0]=0.
第二次读入2，此时读入的数据量为2个，变成这样
C[1] C[2] C[3] C[4] C[5] C[6] C[7] C[8]
0 0 1 1 0 0 0 0
可以看到sum(C[1],C[3])=1，任然不存在比它小的数，但此时输入的数据总量为2，而2-1=1，就是说，存在一个数在2之前并且大于2，这个数当然就是3，我们另b[1]=1.
第三次读入1，此时读入的数据量为3，变成这样
C[1] C[2] C[3] C[4] C[5] C[6] C[7] C[8]
0 1 1 1 0 0 0 0
可以看到sum(C[1],C[2])=1，任然不存在比它小的数，但此时输入的数据总量为3，而3-1=2，就是说，存在两个数在1之前并且大于1，这个数当然就是2，3，我们另b[2]=2.
到此，我们已经算出了每个数前面的较大的数的个数了，数据存在num[]中，现在我们再反过来，先插入1，再插入2，再插入3，但这次我们不再用总数减去sum了，而直接求sum，求出来的自然就是，每个数后面的较小的数的个数，然后将得到的数值累加到相应的b[i]中，最终我们会得到b[0]=2,b[1]=2,b[2]=2,分别对应num[0]=3,num[1]=2,num[2]=1。
之后就是求和而已了，代码如下：
#include<iostream> #include<string.h> #define MAX 1000010 #define N 100010 using namespace std; int C1[MAX],C2[MAX],b[MAX]; int num[N]; long long total[N],ans; int lowbit(int x) { return x&(-x); } void add(int pos,int num,int *C) { while(pos<=MAX) { C[pos]+=num; pos+=lowbit(pos); } } int Sum(int pos,int *C) { int sum=0; while(pos>0) { sum+=C[pos]; int a=lowbit(pos); pos-=lowbit(pos); // cout<<"yufan:"<<pos<<" "<<a<<endl; } return sum; } void init() { total[0]=0; for(int i=0; i<=N; i++) { total[i] = total[i-1]+i; } } int main() { int i=0; int n=0; init(); memset(C1,0,sizeof(C1)); memset(C2,0,sizeof(C2)); cin>>n; for(i=0; i<n; i++) { cin>>num[i]; add(num[i]+1,1,C1); b[i]=i-Sum(num[i],C1); cout<<Sum(num[i],C1)<<endl; b[i]=b[i]-(Sum(num[i]+1,C1)-Sum(num[i],C1)-1); } for(i=n-1;i>=0;i--) { add(num[i]+1,1,C2); b[i]=b[i]+Sum(num[i],C2); } ans=0; for(i=0;i<n;i++) { ans+=total[b[i]]; } cout<<ans; return 0; }
