首页 > 代码库 > HDU 4911

HDU 4911

http://acm.hdu.edu.cn/showproblem.php?pid=4911

一场多校的签到题,树状数组离散化求逆序数

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef __int64 ll ;int n,k ;int tree[100005],b[100005] ;struct node{    int num,id ;}a[100005] ;int lowbit(int x){return x&(-x) ;}void update(int i,int x){    while(i<=n)    {        tree[i]+=x ;        i+=lowbit(i) ;    }}int sum(int i){    int res=0 ;    while(i>0)    {        res+=tree[i] ;        i-=lowbit(i) ;    }    return res ;}int cmp(node aa,node bb){    return aa.num<bb.num ;}int main(){    ll ans ;    while(~scanf("%d%d",&n,&k))    {        for(int i=1 ;i<=n ;i++)        {            scanf("%d",&a[i].num) ;            a[i].id=i ;        }        memset(tree,0,sizeof(tree)) ;        memset(b,0,sizeof(tree)) ;        sort(a+1,a+n+1,cmp) ;        b[a[1].id]=1 ;        for(int i=2 ;i<=n ;i++)        {            if(a[i].num==a[i-1].num)b[a[i].id]=b[a[i-1].id] ;            else b[a[i].id]=i ;        }        ans=0 ;        for(int i=1 ;i<=n ;i++)        {            update(b[i],1) ;            ans+=sum(n)-sum(b[i]) ;        }        printf("%I64d\n",ans-k>0?ans-k:0) ;    }    return 0 ;}
View Code

 

HDU 4911