POJ 3067 原来是树状数组--真的涨姿势

题意：计划在东边的城市和西边的城市中建路，东边的点从1.....n，西边的点从1......m,求这些点连起来后有多少个交叉。

PS：这个题目没有任何思路，没想到是树状数组。。。。

交叉出5个点

分析：3，1肯定能和1与2,3,4连线，2与2,3,4的连线相交。即x,y连线肯定和a(小于x)，b(大于y)的连线，或者a(大于x)，b(小于y)的连线相交。就看有几条这种连线。因此可以先排序，然后直接看当前x,y的前边比y大的数目有几个.就是逆序对数，可参考POJ2299和POJ2352

 ///逆序对数是求前边有几个比当前更大的数字

 ///POJ2352  是求前边有几个比当前更小的数字

 ///按照从大到小排序后求前边有几个次序比他更小的就是逆序对数

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 #define repu(i, a, b) for(int i = a; i < b; i ++)

 using namespace std;

 const int MAXN = ;

 ll c[MAXN];

 int n,m;

 struct S

 {

     int x,y;

     bool operator < (const S& s) const

     {

         if(x == s.x)

             return y < s.y;

         else

             return x < s.x;

     }

 } a[MAXN];

 int b[MAXN];

 int lowbit(int x)

 {

     return x&(-x);

 }

 ll getsum(int i)

 {

     ll s = ;

     while(i>)

     {

         s += c[i];

         i -= lowbit(i);

     }

     return s;

 }

 void add(int li)

 {

     while(li<=m)///并不明白这里的结束条件是什么

     {

         c[li] += 1ll;

         li += lowbit(li);

     }

 }

 int main()

 {

     int T,kase = ;

     scanf("%d",&T);

     while(T--)

     {

         int k;

         scanf("%d%d%d",&n,&m,&k);

         int x,y;

         memset(c,,sizeof(c));

         for(int i=; i<=k; i++)

             scanf("%d%d",&a[i].x,&a[i].y);

         ll sum = ;

         sort(a+,a+k+);

         for(int i=; i<=k; i++)

         {

             add(a[i].y);

             sum += i-getsum(a[i].y);

         }

         kase++;

         printf("Test case %d: %lld\n",kase,sum);

     }

     return ;

 }

转化之后也是逆序对数