AtCoder Beginner Contest 181, E : Transformable Teacher

問題文

　https://atcoder.jp/contests/abc181/tasks/abc181_e

問題概要

　奇数 $N$ について $N$ 個の正整数 $H_i$ と，$M $ 個の正整数 $W_i$ が与えられる．$W$ の要素を一つ $H$ に追加してからソートしたときの，隣接する奇数番目の要素と偶数盤面の要素の差の絶対値の総和の最小値を求めよ．

制約

• $1 \leq N, M \leq 2 \times 10^5$

解法

　原文に書いてないことまで概要で言ってしまっていますが，答えというのは，ソートして隣接要素同士の差をとってから和をとった値です．よって，$W$ から選ぶ要素が決まっていれば，線形時間で答えを求めることができます．
　$W$ の 2 つの（位置が）異なる要素に着目して，それぞれ $H$ に添加したときの状況について考えてみます，2 つの要素が（$H$ をソート済みの順序で）位置 $i, j$ にそれぞれ挿入されるとします．（一般性を失わずに $i < j$ とします）．このとき，位置 $i$ より左側での差と和のとり方は全く変わらないことが分かります．同様のことが，位置 $j$ に着目してからの右側についても言えます．よって，左から $i - 1$ 個を端から順にマッチさせて差の和をとった値及び，右から順に端から順にマッチさせて差の和をとった値を前計算しておけば，これは各 $w \in W$ に関する計算時に使い回すことができます．なので，この左右についてのコストの情報を累積和でもっておくと，各挿入位置について $W$ に影響されない部分のコストを $O( 1 )$ 時間で求めることができるようになります．$W$ と関係す部分というのは $w \in W$ と組になる要素 1 つで，挿入位置は二分探索によって $O( \log N )$ 時間で求められます．よって，全体では $O( N + M \log N )$ 時間で答えを求めることができます．

コード

constexpr auto INF = LIM< LL >::max() / 2;

int main()
{

	IN( int, N, M );
	VI H( N ), W( M );
	cin >> H >> W;
	sort( ALL( H ) );
	sort( ALL( W ) );

	VT< LL > from_head( N + 1 ), from_tail( N + 1 );
	for ( int i = 2; i <= N; i += 2 )
	{
		from_head[i] = H[ i - 1 ] - H[ i - 2 ] + from_head[ i - 2 ];
	}
	reverse( ALL( H ) );
	for ( int i = 2; i <= N; i += 2 )
	{
		from_tail[i] = H[ i - 2 ] - H[ i - 1 ] + from_tail[ i - 2 ];
	}
	reverse( ALL( from_tail ) );
	reverse( ALL( H ) );

	LL res = INF;
	FOR( w, W )
	{
		const int pos = lower_bound( ALL( H ), w ) - begin( H );
		if ( pos % 2 == 0 )
		{
			chmin( res, from_head[ pos ] + from_tail[ pos + 1 ] + abs( w - H[ pos ] ) );
		}
		else
		{
			chmin( res, from_head[ pos - 1 ] + from_tail[ pos ] + abs( w - H[ pos - 1 ] ) );
		}
	}
	cout << res << endl;

	return 0;
}