1990.cpp

poj上第1990题目源码

//对v(i)排序，求出当前小于x的坐标和，和个数
#include<stdio.h>
#include<memory.h>
#include<algorithm>
using namespace std;

struct Point
{
	int x,v;
};
Point point[20001];
__int64 ans = 0;

bool cmp(Point a,Point b)//对v排序
{
	if(a.v<b.v || (a.v == b.v && a.x < b.x))return true;
	return false;
}
int lowbit(int num)
{
	return num&(num^(num-1));
}
void Modify(int array[],int pos,int num,int n)
{
	while(pos <= n)
	 {
	 	array[pos]+=num;
	 	pos += lowbit(pos);
	 }
}
int query(int array[],int end)
{
	int sum = 0;
	while(end>=1)
	{
		sum += array[end];
		end -= lowbit(end);
	}
	return sum;
}
int main()
{
	int n,i,count,total,alltotal,bigtotal,xmax;
	int xtotal[20001];
    int xcount[20001];
    __int64 temp;
    xmax = 0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		  scanf("%d%d",&point[i].v,&point[i].x);
		  if(point[i].x>xmax)
		     xmax = point[i].x;
    }
	sort(point,point+n,cmp);
	memset(xcount,0,sizeof(xcount));
	memset(xtotal,0,sizeof(xtotal));
	Modify(xcount,point[0].x,1,xmax);
	Modify(xtotal,point[0].x,point[0].x,xmax);
	alltotal = point[0].x;
//	printf("%d %d\n",point[0].x,point[1].x);
	for(i=1;i<n;i++)
	{
		count = query(xcount,point[i].x);
		total = query(xtotal,point[i].x);
		bigtotal = alltotal - total;
		temp = (2*count - i)*point[i].x -total + bigtotal;
		ans += point[i].v*temp;
//		printf("%d %d %I64d \n",count,total,ans);
		alltotal += point[i].x;
		Modify(xcount,point[i].x,1,xmax);
		Modify(xtotal,point[i].x,point[i].x,xmax);
	}
	printf("%I64d\n",ans);
	return 0;
}