本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这一题一开始是胸有成竹的，本想1A的，但是接二连三的wa了好几次。。。把我满满的自信心消磨殆尽了。。我一遍一遍的寻找错误，就是找不到。。最后实在没办法要了后台的数据。。运行一看。令我大跌眼眶。。。。竟然都对了，，但为什么WA呢？可能是这一题判题写错了？，最后在不抱希望的情况下我把%I64d改成了%lld，竟然AC了，苦逼的孩子。。oj竟然不支持%I64d.....
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#define N 1000005
using namespace std;
int s[N];
int kp[N];
int a[N];
int tot;
typedef long long L;
int lowbit(int x)
{return x&(-x);
}
void update(int x)
{while(x<N){ s[x]++;x+=lowbit(x);}
}
L Quary(int x)
{ L sum=0;while(x>0){ sum+=s[x];x-=lowbit(x);}return sum;
}
int lisan(int x)
{ int l=1,r=tot;while(l<=r){ int mid=(l+r)>>1;if(a[mid]==x) return mid;else if(a[mid]<x) l=mid+1;else if(a[mid]>x) r=mid-1;}
}
int main()
{ int T;//freopen("d:\\1.txt","r",stdin);//freopen("d:\\2.txt","w",stdout);scanf("%d",&T);while(T--){ memset(s,0,sizeof(s));int n;scanf("%d",&n);tot=0;for(int i=1;i<=n;++i){scanf("%d",&kp[i]);a[i]=kp[i];}sort(a+1,a+n+1);for(int i=1;i<=n;++i)if(i==1||a[i]!=a[i-1])a[++tot]=a[i];L res=0;for(int i=1;i<=n;++i){ int num=lisan(kp[i]);update(num);res+=i-Quary(num);}printf("%lld\n",res);}return 0;
}
这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=117树状数组求逆序数+离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
