poj3067详解——树状数组

Japan

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 32106		Accepted: 8633

Description

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

---

题意：两对岸，一边n个点，一边m个点，现在连k条线，问有几个交点。

梳理一下这其实是一个问逆序对的问题，为什么是逆序对？

举例：

依题意可得上图，算出5个点，除了作图还有什么方法可以得到答案呢？我们不妨先把n的元素看成是有序的，例子就是如此（1 2 3 3）对应的是（4 3 2 1）因为有相同的数据存在，相同位的从小到大排序（4 3 1 2），如果这个结果是（1 2 3 4）的话，是不是就没有交点了，因为没有逆序对存在，把逆序对互换直到为零，操作步数就是5，其实每添加一条线，增加的点数就是增加的逆序对数，还无法理解就按上述步骤模拟几组数据，明白要干什么。

剩下的就是非常经典的求逆序对问题了，如果代码无法理解，看这个https://blog.csdn.net/noscread/article/details/81279516

其实是一个意思。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll sum;
int t,n,m,k;
int num[N],tree[N];
struct node
{
    int a,b;
}line[N];
bool cmp(node x,node y)
{
    if(x.a==y.a) return x.b<y.b;
    else return x.a<y.a;
}
void build(int x)
{
    for(int i=x;i<=m;i+=lowbit(i))
        tree[i]++;
    return ;
}
int get_sum(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))
        res+=tree[i];
    return res;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int cas=1;
    scanf("%d",&t);
    while(t--){
        memset(tree,0,sizeof(tree));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=k;i++)
            scanf("%d%d",&line[i].a,&line[i].b);
        sort(line+1,line+k+1,cmp);
        //for(int i=0;i<k;i++)
            //printf("line[%d]=%d\n",i,line[i].b);
        sum=0;
        for(int i=1;i<=k;i++){
            build(line[i].b);
            sum+=i-get_sum(line[i].b);
        }
        printf("Test case %d: %I64d\n",cas++,sum);
    }

    return 0;
}