読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

POJ 1990 : MooFest

概要

N 匹の牛が一直線上に並んでおり、各牛について、その聴力と x 座標が与えられる。
異なる二頭の牛同士は、座標の差(の絶対値)に大きい方の聴力を乗じた音量で会話をする。
全ての牛が会話をした場合の音量の総和を求めよ。

解法

牛を順番に処理する際、それまでに処理した全ての牛を対象に座標の差を取れば全ての組み合わせについて処理ができます。
このとき、牛を聴力の昇順に処理することで、乗じるべき値が一意に定まります。

次に、着目する牛と、対象となる牛の座標の差の総和を高速に求めることを考えます。
着目している牛の座標を x として、それより左にいる牛の座標を a とします。
このとき、座標の差は x - a です。
複数の牛については、左にいる牛の数を n 、その座標を a_i ( 1-indexed ) として、
n \times x - \sum_{ i = 1 }^{ n } a_i
とすると求まります。
右にいる牛についても同様にして、
\sum_{ i = 1 }^{ n } a_i - n \times x
で求まります。
従って、座標と頭数の総和が分かれば計算できるので、これらを Binary Indexed Tree を用いて高速に求められるようにします。
int オーバーフローに気を付けて先程の式を元に総和を取れば O( n log n ) で答えが求まります。

コード

typedef long long LL;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

struct BIT
{
	vector< LL > data;
	int n;

	BIT( int n ) : data( n + 1, 0 ), n( n )
	{
		return;
	}

	LL sum( int l, int r )
	{
		return sum_( r ) - sum_( l );
	}

	LL sum_( int i )
	{
		LL res = 0;
		
		while ( 0 < i )
		{
			res += data[i];
			i -= i & -i;
		}

		return res;
	}

	void add( int i, int x )
	{
		while ( i <= n )
		{
			data[i] += x;
			i += i & -i;
		}

		return;
	}
};

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	vector< PII > as( n );

	int maxx = 0;

	REP( i, 0, n )
	{
		cin >> as[i].fst >> as[i].snd;

		maxx = max( maxx, as[i].snd );
	}

	sort( ALL( as ) );

	BIT volumes( maxx ), counts( maxx );

	LL res = 0;

	REP( i, 0, n )
	{
		LL tmp = 0;

		tmp += as[i].snd * counts.sum( 0, as[i].snd - 1 ) - volumes.sum( 0, as[i].snd - 1 );
		tmp += volumes.sum( as[i].snd, maxx ) - as[i].snd * counts.sum( as[i].snd, maxx );
		
		res += tmp * as[i].fst;
		
		volumes.add( as[i].snd, as[i].snd );
		counts.add( as[i].snd, 1 );
	}

	cout << res << endl;
	
	return 0;
}