misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 2838 Cow Sorting

http://acm.hdu.edu.cn/showproblem.php?pid=2838
#include<iostream>
#define MAX 100001
#include <algorithm>
#define lowbit(x) (x&(-x))
using namespace std;

__int64 sum[MAX],tree[MAX];
int sum1[MAX],tree1[MAX];
typedef struct
{
  int data;
  int pos;
}point;

bool GY (point a , point b)
{
  return a.data < b.data;
}

__int64 query(int x)
{
    __int64 sum = 0;
    while (x > 0)
    {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int a,int b,int n)
{
    while (a <= n)
    {
        tree[a] += b;
        a += lowbit(a);
    }
}


int query1(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += tree1[x];
        x -= lowbit(x);
    }
    return sum;
}

void add1(int a,int b,int n)
{
    while (a <= n)
    {
        tree1[a] += b;
        a += lowbit(a);
    }
}


int main()
{
    int n , i;
    __int64 ans , x , k;
    point p[ MAX ];
    while (scanf("%d",&n) == 1)
    {
        tree[0] = sum[0] = 0;
        tree1[0] = sum1[0] = 0;

        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[ i ].data);
            p[ i ].pos = i;
            sum[i] = sum[i-1] + p[ i ].data;
            tree[i] = sum[i] - sum[i - lowbit(i)]; 

            sum1[i] = sum1[i-1] + 1;
            tree1[i] = sum1[i] - sum1[i - lowbit(i)];
        }
        sort (p + 1 , p + n + 1 , GY);

        ans = 0;
        for (i = 1;i <= n;++ i)
        {
            k = query (p[ i ].pos - 1);
            if (k)
            {
               x = query1 (p[ i ].pos - 1);
               ans = ans + k + x * p[ i ].data;
            }
           add (p[ i ].pos , - p[ i ].data , n);
           add1 (p[ i ].pos , - 1 , n);
        } 
        printf ("%I64d\n" , ans);
    }
    return 0;
}

posted on 2010-03-26 12:21 此最相思 阅读(513) 评论(0)  编辑 收藏 引用


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