neu 1438 树状数组求逆序数 博客分类： acm acm

#include <bits/stdc++.h>
using namespace std;
#define lowbit(i) i&(-i)
const int N = 1000000 +10;
int n,m,k,l,r;
int a[N];
int getsum(int i)
{
    int xx = 0;
    while(i>0)
    {
        xx+=a[i];
        i-=lowbit(i);
    }
    return xx;
}
void update(int i,int val)
{
    while(i<=N)
    {
        a[i]+=val;
        i+=lowbit(i);
    }
    return ;
}
struct p
{
    int pt,sd;
}num[N];
int cmp(p a,p b)
{
    if(a.pt==b.pt)
        return a.sd < b.sd;
    else return a.pt > b.pt;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&num[i].pt,&num[i].sd);
        }
        sort(num+1,num+1+n,cmp);
        long long  xx = 0;
        for(int i=1;i<=n;i++)
        {
            xx+=getsum(num[i].sd-1);
            update(num[i].sd,1);
        }
        printf("%lld\n",xx);
    }
    return 0;
}