Codeforces #367 Div2 E. Working routine

これは問題設定から気づくべきだったか…。
http://codeforces.com/contest/706/problem/E

問題

N*Mの整数行列が与えられる。
ここに対し、２つの矩形範囲の内容をスワップするクエリがQ個与えられる。
(ただし、２つの範囲は共通部分を持たない他、隣接もしないことが保証されている)

クエリ完了後の行列を答えよ。

解法

愚直に行うとO(NMQ)なので当然TLEする。
ここでは２つの範囲が隣接しない点を利用しよう。

２つの矩形をスワップというが、矩形内の隣接要素同士の関係は境界以外では変化しない。
そこで境界周辺だけ処理することを考えよう。

行列について上下方向及び左右方向をそれぞれ双方向リンクリストでつないでおく。
すると各クエリに対し境界部分だけリンクリストのつなぎ替えを行えば、スワップが完了する。
こうするとO((N+M)Q)で間にあう。

int H,W,Q;
int A,B,C,D,h,w;
struct node { int v; node *L,*R,*U,*D;};
node V[1010][1010];

node* walk(int y,int x) {
	node* n=&V[0][0];
	while(y--) n=n->D;
	while(x--) n=n->R;
	return n;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	scanf("%d%d%d",&H,&W,&Q);
	FOR(y,H) FOR(x,W) scanf("%d",&V[y+1][x+1].v);
	FOR(y,H+2) FOR(x,W+2) {
		if(x<W+1) V[y][x].R=&V[y][x+1];
		if(x>0) V[y][x].L=&V[y][x-1];
		if(y<H+1) V[y][x].D=&V[y+1][x];
		if(y>0) V[y][x].U=&V[y-1][x];
	}
	
	while(Q--) {
		scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&h,&w);
		
		node *n1 = walk(A,B);
		node *n2 = walk(C,D);
		FOR(i,w) {
			swap(n1->U,n2->U);
			n1->U->D=n1;
			n2->U->D=n2;
			n1=n1->R;
			n2=n2->R;
		}
		n1=n1->L;
		n2=n2->L;
		FOR(i,h) {
			swap(n1->R,n2->R);
			n1->R->L=n1;
			n2->R->L=n2;
			n1=n1->D;
			n2=n2->D;
		}
		n1=n1->U;
		n2=n2->U;
		FOR(i,w) {
			swap(n1->D,n2->D);
			n1->D->U=n1;
			n2->D->U=n2;
			n1=n1->L;
			n2=n2->L;
		}
		n1=n1->R;
		n2=n2->R;
		FOR(i,h) {
			swap(n1->L,n2->L);
			n1->L->R=n1;
			n2->L->R=n2;
			n1=n1->U;
			n2=n2->U;
		}
	}
	
	FOR(y,H) {
		node *n = walk(y+1,1);
		FOR(x,W) _P("%d%c",n->v,(x==W-1)?'\n':' '), n=n->R;
	}
}

まとめ

隣接しない、という条件から隣接セル同士をガチャガチャいじるという発想に至るべきであった。