首页 > 代码库 > 树状数组求逆序数(模板)
树状数组求逆序数(模板)
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int MAX = 100005; int a[MAX] , cnt[MAX] , leftMax[MAX] ; int leftMin[MAX] ,rightMax[MAX] , rightMin[MAX]; int lowbit(int x) { return x&(-x); } void update(int x , int y) { while(x <= MAX) { cnt[x] += y; x += lowbit(x); } } int sum(int x) { int sum = 0; while(x) { sum += cnt[x]; x -= lowbit(x); } return sum; } int main() { int t,i,j; scanf("%d" , &t); while(t--) { int n; scanf("%d" , &n); for( i = 1 ; i <= n ; i++) scanf("%d" , &a[i]); memset(cnt , 0 , sizeof(cnt));//清零 for( i = 1 ; i <= n ; i++) { update(a[i] , 1); leftMin[i] = sum(a[i]-1);//计算左边小的个数 leftMax[i] = i - leftMin[i] -1;//计算左边大的个数 // leftMax[i] = sum(MAX) - sum(skill[i]);//计算左边大的个数 } memset(cnt , 0 , sizeof(cnt));//注意此处要再次清零 for( i = n,j = 1 ; i >= 1 ;j++, i--) { update(a[i] , 1); rightMin[i] = sum(a[i]-1);//计算右边小的个数 rightMax[i] = j - rightMin[i]-1;//计算右边大的个数 // rightMax[i] = sum(MAX) - sum(skill[i]);//计算左右大的个数 } __int64 sum = 0; for( i = 1 ; i <= n ; i++) { sum += leftMax[i]*rightMin[i] + leftMin[i]*rightMax[i];//交叉相乘取和 } printf("%I64d\n" , sum); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。