（树状数组）POJ

原题链接：http://poj.org/problem?id=3067

题意：左右两条边，分别有n和m 个城市，现在有k条线把左右各一个城市连接起来，问所有的边的交点。

分析：一开始我想用二维树状数组做，就是求在两点交错的边，在二维矩阵中就是找其中一个点去掉右下角子矩阵之外的和，如图，要求的就是粉色部分。

但是因为本身对树状数组还理解还不够透彻，虽然过了样例，但是对于add和sum的细节还不够了解。

无奈，看了题解，才恍然大悟，其实就是一个求逆序数的题目，只需要一维的树状数组即可。

用结构体记录每条边，优先从左点排序，其次右点。这样左右点都是顺序的了，只要再遍历一次所有边即可。

因为在遍历的过程中，左边的点已经是顺序，所以已经可以确保新加入的左点是在前一个点的下面，所以只需要统计右点中，在新加入的点下面已经加入的点的个数即可，而个数=已经加入右边的个数-在新点上面的右点的个数（i-sum(node[i].r)）

这题很巧妙的通过人为规定一个顺序把，题目化为一个较为简单的一维树状数组求逆序题。

注：有兴趣的可以试试二维树状数组，说不定可以0.0

代码：

 1 const int maxn = 1025;
 2 ll bit[maxn];
 3 int n,m;
 4 struct Node{
 5     int l,r;
 6     bool operator<(const Node &a)const{
 7         if(l==a.l)return r<a.r;
 8         else return l<a.l;
 9     }
10 }node[maxn*maxn];
11 int lowbit(int x) {
12     return x&-x;
13 }
14 
15 ll sum(int x) {
16     int ret = 0;
17     while(x>0){
18         ret+=bit[x];
19         x-=lowbit(x);
20     }
21     return ret;
22 }
23 
24 void add(int x, int d) {
25     while(x<=m){
26         bit[x]+=d;
27         x+=lowbit(x);
28     }
29 }
30 
31 void solve() {
32     int t;
33     int q;
34     int s=0;
35     scanf("%d",&t);
36     while(t--) {
37         scanf("%d%d%d",&n,&m,&q);
38         memset(bit,0,sizeof(bit));
39         int x,y;
40         ll ans=0;
41         for(int i=0; i<q; i++) {
42             scanf("%d%d",&node[i].l,&node[i].r);
43         }
44         sort(node,node+q);
45         for(int i=0;i<q;i++){
46             ans+=i-sum(node[i].r);
47             add(node[i].r,1);
48         }
49         printf("Test case %d: %I64d
",++s,ans);
50     }
51 }