前几天开始看树状数组了，然后开始找题来刷。
首先是 POJ 2299 Ultra-QuickSort： http://poj.org/problem?id=2299
这题是指给你一个无序序列，只能交换相邻的两数使它有序，要你求出交换的次数。实质上就是求逆序对，网上有很多人说它的原理是冒泡排序，可以用归并排序来求出，但我一时间想不出它是如何和归并排序搭上边的（当初排序没学好啊~），只好用刚学过的树状数组来解决了。在POJ 1990中学到了如何在实际中应用上树状数组，没错，就是用个特殊的数组来记录即可，然后区间查询和单点更新的复杂度都在O(logn)范围内。
对于这道题，即处理到第i个数时，可以通过计算 i-1-它前面比它小的数得出前面比它大的数，即该数前面的逆序数；而统计某数前面比它小的数就是树状数组的裸题了。分析到这里已经差不多了，但是一看，a[i] ≤ 999,999,999，就不能简单地用数组下标来记录a[i]的值了，这时我想起了之前看过的一个很高大上的名字："离散化"，没错，就是离散化，因为n < 500,000而已，用不着那么多数组的空间，把a[i]通过排序再放进数组即可，不过具体的题我还没做过，对于这道题，我的做法是设置一个辅助数组 r[i] 表示第i个数的下标，初始化时也就是r[i]= i，然后通过比较对应a[i]的a[j]的值对r[]排序。说白了就是对数组a[]的下标进行排序（利用了刘汝佳小白书上kruskal的做法），这时候数组r[]的逆序数就是数组a[]的逆序数。这是因为在排序时是一一对应的，每交换两个数使a[]消除一个逆序对时r[]便增加一个逆序对（r[]本来是1,2,3,4,5……的顺序数列），所以就转化为了求数组r[]的逆序对，此时下标只受n<500,000约束，开数组不成问题，详见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL maxn= ; inline int lowbit(int x) { return x&(-x); } struct treeArray{
int c[maxn], n;
treeArray(int n=):n(n) { memset(c,,sizeof(c)); }
void clear() { memset(c,,sizeof(c)); }
int sum(int x) const {
int ans= ;
while(x){
ans+= c[x];
x-= lowbit(x);
}
return ans;
}
void add(int x, int d){
while(x<=n){
c[x]+= d;
x+= lowbit(x);
}
}
} num(maxn); int a[maxn], r[maxn];
bool cmp(int i, int j) { return a[i]<a[j]; } int main(){
int n,i;
while(~scanf("%d",&n),n){
for(i=; i<=n; ++i){
scanf("%d",a+i);
r[i]= i;
}
sort(r+,r+n+,cmp);
LL inv= ;
num.clear();
num.n= n;
for(i=; i<=n; ++i){
inv+= i--num.sum(r[i]);
num.add(r[i],);
}
printf("%lld\n",inv);
}
return ;
}
树状数组的写法我参照了网上的人的写法，把它封装成一个结构体，用于实现区间查询和单点更新的数组c[]放在了结构体内，这样子可使代码更清晰，不至于要开个全局数组容易混淆，如同矩阵快速幂一样把矩阵的乘法重载在结构体中，可以避免在一些细节上浪费精力，代码量也没有增加多少。
然后是第二道 POJ 3067： http://poj.org/problem?id=3067
这题主要是说东西两边各有1~N和1~M个城市，然后有K条道路连接东西两边的城市，要求这K条边的所有交点。这里有个不大却很易栽的坑：K的范围没给出，所以可以猜想其为N*M的上限，然后它给出的道路也没说是有序的（千万别被样例骗了），所以我们首先要对它进行预处理才行。
如上题一样，可以利用求逆序对的做法来求。为什么呢？我们可以先按e（就是左边的坐标）排升序，e相同的话按w（右边的坐标）排升序（w一定要为升序，因为e相同时的边是不会有交叉点的，所以w升序在统计时可以使e相同而w不同的边不存在逆序对，符合没有交叉点的实际情况），大体的预处理就是这样，然后对排好序的w边进行求逆序数即可，具体求法如上题所述。和上题不同的是，这里的w值可以和前面的重复，但也不影响树状数组的运用，要处理好细节，记住先返回区间的值即sum(x)，再去更新即add(x)（数组c[x]在add(x)前为0，不影响sum(x)的统计）。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
#define lowbit(x) ((x)&-(x))
const int maxn= ; struct treeArray{
int c[maxn], n;
treeArray(int n=):n(n) { memset(c,,sizeof(c)); }
void clear() { memset(c,,sizeof(c)); }
LL sum(int x) const {
LL ans= ;
while(x){
ans+= c[x];
x-= lowbit(x);
}
return ans;
}
void add(int x, int d){
while(x<=n) { //这里是 wa的根源？
c[x]+= d;
x+= lowbit(x);
}
}
} num(maxn); struct Edge{
int e,w;
bool operator <(const Edge E2) const {
if(e==E2.e) return w<E2.w;
return e<E2.e;
}
} edge[maxn]; void solve(){
static int p=;
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=; i<=k; ++i)
scanf("%d%d",&edge[i].e, &edge[i].w); sort(edge+,edge+k+);
LL inv= ;
num.clear();
num.n= m; //原来这里才是 wa的根源！！
for(int i=; i<=k; ++i){
inv+= i--num.sum(edge[i].w);
num.add(edge[i].w,);
}
printf("Test case %d: %lld\n",++p,inv);
} int main(){
int t;
scanf("%d",&t);
while(t--) solve();
return ;
}
奇怪的是，这题我wa了近10遍才过(T.T)，一开始怎么也找不着错的原因，各种long long、__int64、%lld、%I64d的输入输出姿势都试过了，还是wa，没办法，只好和标程一点一点地对拍，到最后才发现真正的错误是在num.n= m这里，就是没处理好树状数组c[]的n，这种细节问题还是第一次见，不过也需记住这个错误，因为树状数组的结构体模板以后应该会经常用到，还是得多刷题了，昨晚竟被老师和师兄说自己的进度太慢，听后除了惭愧外还有一丝恨铁不成钢（我对自己）的心理，大白书，Come on！