用三個(gè)樹狀數(shù)組維護(hù)一下：比a[i]小的數(shù)有多少、前i個(gè)數(shù)之和是多少、比a[i]小的數(shù)之和是多少。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 9:33:01
* File Name: hdu2838.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(100007);
int n;
int64 ans,bit[kMaxn],bit2[kMaxn],bit3[kMaxn];
void Add(int64 *a,int x,int delta)
{
for(int i=x;i<=n;i+=lowbit(i))
a[i]+=delta;
}
int64 Sum(int64 *a,int x)
{
int64 re(0);
for(int i=x;i>0;i-=lowbit(i))
re+=a[i];
return re;
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1)
{
ans=0;
memset(bit,0,sizeof(bit));
memset(bit2,0,sizeof(bit2));
memset(bit3,0,sizeof(bit3));
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
Add(bit,t,1);
Add(bit2,i,t);
Add(bit3,t,t);
ans+=(i-Sum(bit,t-1)-1)*t;
ans+=Sum(bit2,i-1);
ans-=Sum(bit3,t-1);
}
cout<<ans<<endl;
}
return 0;
}
posted on 2011-08-02 10:23
lee1r 閱讀(478)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)