心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
用三个树状数组维护一下:比a[i]小的数有多少、前i个数之和是多少、比a[i]小的数之和是多少。
以下是我的代码:
/*
 * 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 阅读(458) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理