Japan【树状数组求逆序对】

  讲到树状数组求逆序数，这已经不是那么的难了，做过了几道题已经可以差不多应对了。

  这道题的难度就在于求逆序数的思路了，尤其是如何处理有相同值（相同东海岸城市）的方式上。

  首先，举个相近的例子就拿4、3、1、2这四个数求逆序数来说，其求得是这四个数每个数前面有几个比它大的数，我们可以看到：对于（4），它的值为0；对于（3），它的值为1（可以看成现在共有的数-包括自己本身不大于的数）；同理可知（1）的逆序数为2（看作3（全体）-1（此时加上自己也就自己不大于自己的数的个数））；最后，（2）的逆序数为2，是（4-2（1和2它本身））。

所以，这一道题也是一样的，我们知道海岸线的东西，不妨就把东边的按升序排，然后看西边的（如果东边相等，就升序，不然求得逆序数偏大），西边的城市序号排出的数列，我们求得它的逆序数即可，至于怎么关联左右连线，我利用的是结构体来衔接。

题面：

Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the venue. Japan is tall island with N cities on the East coast and M cities on the West coast (M <= 1000, N <= 1000). K superhighways will be build. Cities on each coast are numbered 1, 2, ... from North to South. Each superhighway is straight line and connects city on the East coast with city of the West coast. The funding for the construction is guaranteed by ACM. A major portion of the sum is determined by the number of crossings between superhighways. At most two superhighways cross at one location. Write a program that calculates the number of the crossings between superhighways.

Input

The input file starts with T - the number of test cases. Each test case starts with three numbers – N, M, K. Each of the next K lines contains two numbers – the numbers of cities connected by the superhighway. The first one is the number of the city on the East coast and second one is the number of the city of the West coast.

Output

For each test case write one line on the standard output: 
Test case (case number): (number of crossings)

Sample Input

1
3 4 4
1 4
2 3
3 2
3 1

Sample Output

Test case 1: 5

 

完整代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
using namespace std;
typedef long long ll;
struct node
{
    int l,r;
}mp[1000005];
int N,M,K;
bool cmp(node e1, node e2)
{
    return e1.l==e2.l?(e1.r<e2.r):(e1.l<e2.l);
}
int bit[4005];
void update(int i, int x)
{
    while(i<=1001)
    {
        bit[i]+=x;
        i+=lowbit(i);
    }
}
int query(int i)
{
    int res=0;
    while(i)
    {
        res+=bit[i];
        i-=lowbit(i);
    }
    return res;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int Case=1; Case<=T; Case++)
    {
        memset(mp, 0, sizeof(mp));
        memset(bit, 0, sizeof(bit));
        scanf("%d%d%d",&N,&M,&K);
        ll ans=0;
        for(int i=1; i<=K; i++) scanf("%d%d",&mp[i].l,&mp[i].r);
        sort(mp+1, mp+1+K, cmp);
        for(int i=1; i<=K; i++)
        {
            update(mp[i].r, 1);
            ans+=query(M)-query(mp[i].r);
        }
        printf("Test case %d: %lld\n",Case,ans);
    }
    return 0;
}