本文共 2207 字,大约阅读时间需要 7 分钟。
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 56014 | Accepted: 20694 |
Description
Input
Output
Sample Input
59105431230
Sample Output
60
Source
树状数组求逆序数。由于数组元素最大达到999,999,999,所以不能直接开数组,要先用“离散化”的方法将数组元素映射成1~n,再进行一般的树状数组操作。
#include#include #include #include using namespace std;typedef long long ll;const int N = 500005;struct node{ int val,pos;}nod[N];int C[N],r[N];int n;bool cmp(node a,node b){ return a.val < b.val;}int lowbit(int t){ return t&(-t);}void add(int t){ while(t <= n) { C[t] += 1; t += lowbit(t); }}//求得前面小于当前的数的个数int getnum(int t){ int ans = 0; while(t > 0) { ans += C[t]; t -= lowbit(t); } return ans;}int main(){ while(~scanf("%d",&n) && n) { memset(C,0,sizeof(C)); for(int i = 1;i <= n;i++) { scanf("%d",&nod[i].val); nod[i].pos = i; } sort(nod+1, nod+1+n,cmp);//先sort for(int i = 1;i <= n;i++)//离散化处理 r[nod[i].pos] = i; ll ans = 0,k; for(int i = 1;i <= n;i++) { add(r[i]); k = i - getnum(r[i]); ans += k; } printf("%lld\n",ans); } return 0;}
转载地址:http://wqzgf.baihongyu.com/