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; } } }
まとめ
本番「正方形なら楽なのに…」まで思いついたのに、なぜ分割を思いつかなかったのだ。