POJ3067(树状数组:统计数字出现个数)

#include"cstdio"
#include"cstring"
#include"algorithm"
using namespace std;
const int MAXN=1000005;
struct Node{
    int west,east;
}hways[MAXN];
bool comp(const Node &a,const Node &b)
{
    if(a.east != b.east)    return a.east > b.east;
    else return a.west > b.west;
}

int bit[MAXN];
void add(int i,int x)
{
    while(i<MAXN)
    {
        bit[i]+=x;
        i+=i&(-i);
    }
}

long long sum(int i)
{
    long long s=0;
    while(i>0)
    {
        s+=bit[i];
        i-=i&(-i);
    }
    return s;
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        memset(bit,0,sizeof(bit));
        long long ans=0;
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&hways[i].east,&hways[i].west);
        }
        sort(hways,hways+k,comp);
        add(hways[0].west,1);
        for(int i=1;i<k;i++)
        {
            ans+=sum(hways[i].west-1);
            add(hways[i].west,1);
        }
        
        
        printf("Test case %d: %I64d\n",cas,ans);
    }
    
    return 0;
}