原题：POJ 2299
知识：树状数组
题意：一个n个元素的数组，对它进行冒泡排序，输出排序时交换两个数字的次数。
解析：大家都知道，冒泡排序交换的次数就是数组中逆序数（不知道问度娘）之和，如果通过枚举，N^N直接做这题，肯定会T。你可以参考百度求逆序数的方法——并归，不过这里讲一下用树状数组的做法。
求逆序数之和就是求ΣC[i]，（C[i]代表第i个数后面比它小的数），稍微思考一下，它也就等于求ΣD[i]，（D[i]代表第i个数前面比它大的数），这个就自己思考，不多讲了。
那怎么求ΣD[i]呢？
举个例子，2 5 3 7，我们从小往大算每个数的D[i]
第一个是2，前面有0个比2大的，D[1]==0；
第二个是3，前面有1个比3大的，D[2]==1；
第三个是5，前面有0个比2大的，D[3]==0；
第四个是7，前面有0个比7大的，D[4]==0；
这是一个怎么样的过程呢？
- 我们给原数组2 5 3 7的位置点一盏灯，1 1 1 1
- 我们按数字从小到大灭灯
- 首先灭2，0 1 1 1，如果统计2的位置前面还有几盏灯没有灭，为0
- 然后灭3，0 1 0 1，发现还有5的位置上的灯没灭，为1
- 然后灭5，0 0 0 1，5位置前面没有灯了，为0
- 最后灭7，0 0 0 0，同样，为0
- 所以0+1+0+0，只需要交换一次
解释一下：
因为从小往大灭灯，所以当灭数字k位置上的灯时，所有还亮着的灯代表的数字都比k要大，要求k的位置前面的比k大的数，同解于，统计k位置前面的还没有灭的灯。
代码实现思路：
代码需要有以下两个功能：
- 可以快速求解k位置前面还有几盏灯，即快速求区间和
- 可以实现快速灭灯，即快速单点更新
可以发现，和树状数组的优点如出一辙。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<cstdlib>
//#include<>
#include<functional>
#define D long long
#define F double
#define MAX 0x7fffffff
#define MIN -0x7fffffff
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define pill pair<int, int>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define for2(i,a,b) for(int i=a;i>=b;i--)
#define ini(n) scanf("%d",&n)
#define inll(n) scanf("%lld",&n)
#define outisp(n) printf("%d ",n)
#define outllsp(n) printf("%lld ",n)
#define outiel(n) printf("%d\n",n)
#define outllel(n) printf("%lld\n",n)
using namespace std;
#define N 500100
#define MOD ((int)1e9+7)
#define random(a,b) (rand()%(b-a+1)+a)
#define stop Sleep(2000)
#define CLS system("cls")
const string el="\n";
const string elel="\n\n";
const string sp=" ";
const string spsp=" ";
const string tab="\t";
int n;
pill x[N];
int tr[N];
D ans;//ans可能非常大，需要用long long
int lowbit(int i){
return i&(-i);
}
void up(int a,int m){//A[a]+=m
while(a<=n){
tr[a]+=m;
a+=lowbit(a);
}
}
int query(int pos){
int sum=0;
while(pos>0){
sum+=tr[pos];
pos-=lowbit(pos);
}
return sum;
}
void process(void){ans=0;
//A数组就是此题树状数组所代表的数组
//mmm(A,1);//所谓的A数组赋初值一
ini(n);if(!n)return ;
for1(i,1,n){
int mid;ini(mid);
x[i]=mk(mid,i);//保存在原数组中的位置
}
sort(x+1,x+1+n);//按照数的大小排序
//排序只是为了得到这些数的大小关系，重要的还是他们在原数组中是位置
for1(i,1,n){//因为A数组值为1，所以tr数组的值就等于tr[i]所代表的数的个数，lowbit(i)
tr[i]=lowbit(i);
}
for1(i,1,n){//对于排序后的数组从小到大过一遍
//把A[i]变成0表示已经访问过了，A[i]前面的（A[1]~A[i-1]）值还为1的个数，就是前面比它大的个数
//因为for循环是从小到大， 变0的顺序也是，所以A[i]变0后还没有变0的就是比它大的数
up(x[i].se,-1); //更新的是在原数组的位置
//1 to 0 , add -1
ans+=query(x[i].se-1);//从1到i-1中1的个数 ，到i也可以，反正A[i]是0
}
outllel(ans);
process();
}
int main(){
process();
return 0;
} 第一次WA在了ans的范围，因为数据最多50万个，假设给你的是50个严格递减的，那么ans应该是50万*（50万+1）/2，int是肯定不行了。
说到这里，你们可能会有个疑问：万一很多个相同的，那灭灯的时候，前面有几个相同的数的位置上还有灯怎么办？
2 2 2，灯为 1 1 1，比如说先灭第二盏，那变成 1 0 1，前面有一个一，为1了，但是我们要求的是前面有几个大于的，不就冲突了吗？
这个我也是AC了才发现的，不过看了一下代码，会心一笑~
pair的sort在first相同时是按照second升序排列的，也就是说，一位置的2和二位置的二，会把一位置的2排在前面先灭，自然不会出现上面的问题了。
上面的代码可以看上去比较累，下面有删除注释版（写到main函数里面了，在其他都一样的情况下，运行结果从370ms变成了400ms，我还没有找原因，如果真的会变快下次全写main外面了）
//同上
int n;
pill x[N];
int tr[N];
D ans;
int lowbit(int i){
return i&(-i);
}
void up(int a,int m){
while(a<=n){
tr[a]+=m;
a+=lowbit(a);
}
}
int query(int pos){
int sum=0;
while(pos>0){
sum+=tr[pos];
pos-=lowbit(pos);
}
return sum;
}
int main(){
while(ini(n),n!=0){
ans=0;
for1(i,1,n){
int mid;ini(mid);
x[i]=mk(mid,i);
}
sort(x+1,x+1+n);
for1(i,1,n){
tr[i]=lowbit(i);
}
for1(i,1,n){
up(x[i].se,-1);
ans+=query(x[i].se-1);
}
outllel(ans);
}
return 0;
}