思路: 树状数组
分析:
1 题目和求逆序数那题很像,裸题
代码:
/************************************************ * By: chenguolin * * Date: 2013-08-21 * * Address: http://blog.csdn.net/chenguolinblog * ***********************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef __int64 int64; const int MAXN = 100010; int n , num[MAXN]; int64 treeNum[MAXN]; int64 treeSum[MAXN]; int lowbit(int x){ return x&(-x); } int64 getSum(int x , int64 *arr){ int64 sum = 0; while(x){ sum += arr[x]; x -= lowbit(x); } return sum; } void add(int x , int val , int64 *arr){ while(x < MAXN){ arr[x] += val; x += lowbit(x); } } int64 solve(){ memset(treeNum , 0 , sizeof(treeNum)); memset(treeSum , 0 , sizeof(treeSum)); int64 ans = 0; int64 total = 0; for(int i = 1 ; i <= n ; i++){ if(i > 1){ ans += total-getSum(num[i]-1 , treeSum); ans += (i-1-getSum(num[i]-1 , treeNum))*num[i]; } total += num[i]; add(num[i] , 1 , treeNum); add(num[i] , num[i] , treeSum); } return ans; } int main(){ while(scanf("%d" , &n) != EOF){ for(int i = 1 ; i <= n ; i++) scanf("%d" , &num[i]); printf("%I64dd\n" , solve()); } return 0; }
时间: 2024-09-22 15:44:16