kmjp's blog

競技プログラミング参加記です

AtCoder ARC #047 : D - ナナメクエリ

Xが縦、Yが横座標に相当する問題苦手。
http://arc047.contest.atcoder.jp/tasks/arc047_d

問題

N*Nのグリッドがある。
左からY列目、上からX行目のセルを(X,Y)と表現する。
初期状態で各セルには0が格納されている。

以下のクエリを順次処理せよ。

  • A≦X+Y≦Bとなる範囲のセル(X,Y)に整数を加算する。
  • A≦X-Y≦Bとなる範囲のセル(X,Y)に整数を加算する。
  • 矩形の範囲(X1,Y1)-(X2,Y2)のセルに含まれる最大値と、その値を持つセルの数を答える。

解法

先頭2つのクエリは、以下の値を処理するだけである。
sum[a] := 1つめのクエリでa=X+Yとなるセル群に加算された数の総和
diff[b] := 2つめのクエリでb=X-Yとなるセル群に加算された数の総和

問題は3つ目のクエリ。
sum[a]とdiff[b]を用いてこのクエリを高速に処理したい。
(X1,Y1)-(X2,Y2)の範囲では、X1+Y1≦a≦X2+Y2である。

そこで、x+y=aとなる矩形内中のセル群(x,y)に対するx-yの集合に対し、diff[x-y]の最大値を求めることを考えよう。
aを少しずつずらすとx-yの範囲が少しずつずれるので、SegTree等でdiff[x-y]の最大値を更新していきつつ、sum[a]と(diff[x-y]の最大値)の和の最大値を求めるとよい。
ただ、これではN=500以下の部分点は取れても満点は取れない。
もう一段高速化が必要である。

クエリの範囲が長方形ではなく正方形(X2-X1==Y2-Y1)だと、aを(X1,Y1)から(X2,Y1)-(X1,Y2)相当まで増加していく間と、逆に(X2,Y2)から(X2,Y1)-(X1,Y2)まで減少させていく間、x-yの範囲が増加する一方である。
そのためSegTreeを使わなくてもdiff[x-y]の最大値を容易に更新できるようになる。
そこで長方形を正方形の集合に分割して処理しよう。

int N,Q;
int arr[40000];
int *S=&arr[10000];
int *D=&arr[30000];

pair<int,int> up(pair<int,int>& a,pair<int,int> b) {
	if(a.first>b.first) return a;
	if(a.first<b.first) return a=b;
	a.second+=b.second;
	return a;
}

pair<int,int> rect(int X1,int X2,int Y1,int Y2) {
	pair<int,int> v={-1<<30,0};
	pair<int,int> best[2]={{-1<<30,0},{-1<<30,0}};
	int x,y;
	for(x=X1;x<=X2;x++) {
		int s=x+Y1;
		int id=s%2;
		up(best[id],{D[Y1-X1+(x-X1)],1});
		if(x!=X1) up(best[id],{D[Y1-X1-(x-X1)],1});
		up(v,{best[id].first+S[s],best[id].second});
	}
	
	best[0]=best[1]={-1<<30,0};
	for(x=X2;x>X1;x--) {
		int s=x+Y2;
		int id=s%2;
		up(best[id],{D[Y2-X2+(X2-x)],1});
		if(x!=X2) up(best[id],{D[Y2-X2-(X2-x)],1});
		up(v,{best[id].first+S[s],best[id].second});
	}
	
	return v;
}


void solve() {
	int i,j,k,l,r,x,y,a,b; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y>>r;
			for(i=x;i<=y;i++) S[i]+=r;
		}
		else if(i==2) {
			cin>>x>>y>>r;
			for(i=x;i<=y;i++) D[i]+=r;
		}
		else {
			
			int X1,X2,Y1,Y2;
			cin>>Y1>>Y2>>X1>>X2;
			
			pair<int,int> v={-1<<30,0};
			while((Y2-Y1+1)*(X2-X1+1)) {
				if(Y2-Y1>=X2-X1) {
					up(v,rect(X1,X2,Y1,Y1+(X2-X1)));
					Y1+=X2-X1+1;
				}
				else {
					up(v,rect(X1,X1+(Y2-Y1),Y1,Y2));
					X1+=Y2-Y1+1;
				}
			}
			cout<<v.first<<" "<<v.second<<endl;
		}
	}
}

まとめ

本番「正方形なら楽なのに…」まで思いついたのに、なぜ分割を思いつかなかったのだ。