CODE FESTIVAL 2014 あさプロHard : C - 宝探し 2

意気揚々と誤回答してしまった。
http://code-festival-2014-morning-hard.contest.atcoder.jp/tasks/code_festival_morning_hard_c

問題

N*Mのグリッドがあり、1～KのK種類のお宝が存在する。
初期状態で座標(i,j)の各マスにはX[i][j]番の宝が埋まっている。
ここで以下のQ個のクエリについて答えよ。

1. 隣接するセル(x1,y1)と(x2,y2)のお宝を入れ替える。
2. (x1,y1)と(x2,y2)を対角線とする長方形の範囲内で、最も数が多い種類のお宝について、種類と数を答える。

解法

２つ目のクエリについては、K通りのお宝の各種類について、長方形の範囲内の数を数えて最大値を求めればよい。

このような処理を行う方法としては、２次元DPが考えられる。
ただし今回の問題では２次元DPではTLEになってしまう。

そこで、各お宝の種類について２次元累積和を使うことを考える。
この場合、２つ目のクエリは１回あたりO(K)で済む。

問題は１つ目のクエリである。
ある２次元整数配列Aにおいて、その累積和をSとする。
A[i][j]を増減した場合、i≦x、j≦yとなる各S[x][y]について同様の増減をする必要がある。
すなわち、S中の長方形の範囲の値を更新することになるので、お宝の追加削除には１回O(N*M)かかってしまう。
これでは間に合わない。

ただ、今回の例ではお宝は隣接マスとしか移動しないことに注意が必要である。
お宝が１マス動く場合、２次元累積和の配列上では、そのお宝の影響範囲となる長方形が上下左右に１マスだけ動くことになる。
よって、更新が必要なのは幅１または高さ１の長方形領域だけであり、O(max(N,M))で済む。

これにより、全体としてO(Q*(K+max(N,M)))で済ませることができる。

ll p[3];
int H,W,K,Q;
int A[502][502];
int S[502][502][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p[0]=1;
	p[1]=1LL<<20;
	p[2]=1LL<<40;
	
	
	cin>>H>>W>>K;
	FOR(y,H) FOR(x,W) cin>>A[y+1][x+1], S[y+1][x+1][A[y+1][x+1]]++;
	FOR(i,101) {
		FOR(y,H) FOR(x,W) S[y+1][x+1][i] += S[y+1][x][i];
		FOR(y,H) FOR(x,W) S[y+1][x+1][i] += S[y][x+1][i];
	}
	
	cin>>Q;
	while(Q--) {
		int x1,y1,x2,y2;
		cin>>l>>y1>>x1>>y2>>x2;
		if(l==1) {
			if(x1==x2) {
				if(y1<y2) {
					for(x=x1;x<=W;x++) S[y1][x][A[y1][x1]]--;
					for(x=x1;x<=W;x++) S[y1][x][A[y2][x2]]++;
				}
				else {
					for(x=x1;x<=W;x++) S[y2][x][A[y1][x1]]++;
					for(x=x1;x<=W;x++) S[y2][x][A[y2][x2]]--;
				}
			}
			else {
				if(x1<x2) {
					for(y=y1;y<=H;y++) S[y][x1][A[y1][x1]]--;
					for(y=y1;y<=H;y++) S[y][x1][A[y2][x2]]++;
				}
				else {
					for(y=y1;y<=H;y++) S[y][x2][A[y1][x1]]++;
					for(y=y1;y<=H;y++) S[y][x2][A[y2][x2]]--;
				}
			}
			swap(A[y1][x1],A[y2][x2]);
		}
		else {
			
			x=y=0;
			FOR(i,101) {
				j = S[y2][x2][i]-S[y2][x1-1][i]-S[y1-1][x2][i]+S[y1-1][x1-1][i];
				if(j>=x) y=i,x=j;
			}
			cout << y << " " << x << endl;
		}
	}
}

まとめ

最初「２次元DPだろ？」と思って勢いよく失敗してしまった。