欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-18 23:36:58
...
#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;
}
相关标签: acm