POJ1990 MooFest

USACO U S Openの問題。数直線上に点がN点与えられ、それらの2点の間のコストが(その間の距離)*(2点の持つ値の大きい方)で定められているので、すべての2点間のコストの総和を求める。

BITを2個持っておいてやって、"座標の合計"と"そこまでにある点の数"を持っておくと通る。
long long トラップが存在して…

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll bit[32769];
ll bit2[32769];
void add(ll a,ll b)
{
	for(;;)
	{
		bit[a]+=b;
		a+=a&-a;
		if(a>32768)
		{
			break;
		}
	}
}
ll sum(ll a)
{
	ll ret=0;
	for(;;)
	{
		ret+=bit[a];
		a-=a&-a;
		if(a==0)
		{
			break;
		}
	}
	return ret;
}
void add2(ll a,ll b)
{
	for(;;)
	{
		bit2[a]+=b;
		a+=a&-a;
		if(a>32768)
		{
			break;
		}
	}
}
ll sum2(ll a)
{
	ll ret=0;
	for(;;)
	{
		ret+=bit2[a];
		a-=a&-a;
		if(a==0)
		{
			break;
		}
	}
	return ret;
}
typedef pair<ll,ll>pii;
int main()
{
	int num;
	scanf("%d",&num);
	vector<pii>vec;
	for(int i=0;i<num;i++)
	{
		ll za,zb;
		scanf("%lld%lld",&za,&zb);
		vec.push_back(make_pair(za,zb));
		add(zb,zb);
		add2(zb,1);
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	ll ret=0;
	for(int i=0;i<num;i++)
	{
		ll now=0;
		now+=sum2(vec[i].second-1)*vec[i].second-sum(vec[i].second-1);
		now+=(sum(32768)-sum(vec[i].second))-(sum2(32768)-sum2(vec[i].second))*vec[i].second;
		ret+=now*vec[i].first;
		add(vec[i].second,-vec[i].second);
		add2(vec[i].second,-1);
	}
	printf("%lld\n",ret);
}