ACM PKU 3067 Japan

树状数组的题，很简单，只是我做了一下午，哈哈！都是因为好久没有写代码了，这是个多组测试数据的题，初始化得注意点；树状数组的思想很简单，先排序，然后找交叉点，交叉点的数目等于A数组相对于x位置右边的sum值。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
using namespace std;
struct node {
        int e,w;
} tmp[1000010];
long long A[1005];
int MAX_N;

bool operator < (const node & a,const node &b)
{
    if(a.e==b.e) return a.w < b.w;
    return a.e<b.e;
}

int lowbit(int x)
{
    return (-x)&x;
}

void add(int x)
{
    for(;x>0;A[x]+=1,x-=lowbit(x));
}

long long  sum(int x){
    long long s=0;
    for(;x<=MAX_N;s+=A[x],x+=lowbit(x));
    return s;
 }
int main()
{
        //freopen("in.txt","r",stdin);
        int n_case,N,M,K;
        long long res;
        scanf("%d",&n_case);
        for(int i=0; i<n_case; i++) {
                scanf("%d%d%d",&N,&M,&K);
                res=0;MAX_N=M;
                memset(A,0,sizeof(A));
                for(int j=0; j<K; j++) {
                scanf("%d%d",&tmp[j].e,&tmp[j].w);
                }
                sort(tmp,tmp+K);
                for(int k=0;k<K;k++)
                {
                     res+=sum(tmp[k].w+1);
                     add(tmp[k].w);
                }
                printf("Test case %d: %I64d\n",i+1,res);
        }
        return 0;
}

 

转载于:https://www.cnblogs.com/Chinese-Coder-Clarence/articles/2415631.html