HackerRank HourRank 27 : C. Moving the Kings

定番テクっぽいな…。
https://www.hackerrank.com/contests/hourrank-27/challenges/moving-the-kings/problem

問題

無限に広いチェス盤のうちN箇所にキングの駒がある。

Q個のクエリが与えられる。
各クエリは盤面の１マスを示している。
各キングをそのマスに向け移動させるための最小手数の総和を求めよ。

解法

マンハッタン距離に関する処理を45度回転させることで容易にするテクと同様、チェビシェフ距離も45度回転させると実質マンハッタン距離のように（回転後の）X座標とY座標の距離を個別に求めるとよくなる。

これらはキングの駒の(回転後の)X座標とY座標それぞれ個別にソートしたうえで累積和を使えば1クエリに対しO(logN)で解ける。
クエリを先にソートしておけば尺取り法も使えるけど、クエリのソートにO(QlogQ)かかるから結局同じか。

int N,Q;
ll X[101010],Y[101010];
ll SX[101010],SY[101010];
ll XS[101010],YS[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		SX[i]=X[i]+Y[i];
		SY[i]=X[i]-Y[i];
	}
	sort(SX,SX+N);
	sort(SY,SY+N);
	FOR(i,N) XS[i+1]=XS[i]+SX[i];
	FOR(i,N) YS[i+1]=YS[i]+SY[i];
	
	FOR(i,Q) {
		cin>>x>>y;
		ll QX=x+y;
		ll QY=x-y;
		
		ll ret=0;
		x=lower_bound(SX,SX+N,QX)-SX;
		y=lower_bound(SY,SY+N,QY)-SY;
		ret+=(QX*x-XS[x]) + (XS[N]-XS[x]-QX*(N-x));
		ret+=(QY*y-YS[y]) + (YS[N]-YS[y]-QY*(N-y));
		cout<<ret/2<<endl;
		
	}
	
}

まとめ

このテクは覚えておかねば。