BOJ 31465 초콜릿 종류 맞히기

문제 링크입니다.

4차 이면체군에 관해

틀 안쪽에서 초콜릿을 섞는 일은 없으니까, 하나의 커다란 판으로 생각합시다. 이 판을 돌리거나 뒤집어도, 각 칸과 판의 네 꼭짓점 사이의 거리 등은 변하지 않고 유지됩니다. 이런 점에서, 우리가 아무리 판을 돌리거나 뒤집더라도 네 꼭짓점의 위치만 알 수 있으면 괜찮습니다. 실제로 가능한 꼭짓점의 배치는 8가지뿐이니 이를 각각 인덱싱해 그 번호를 적절히 바꿔주는 것으로 판을 돌리거나 뒤집는 것을 표현할 수 있습니다.

쿼리 처리하기

각각의 상태에 적절한 인덱스를 부여했다면 그 뒤로는 주어지는 쿼리를 적절한 구간 업데이트로 바꿔서 처리해 주면 됩니다. 느리게 갱신되는 세그먼트 트리를 이용합시다. 구현 상의 편의를 위해 인덱싱을 뒤집음 여부와 회전 정도로 나누었습니다. 뒤집음의 홀짝성과 그에 따른 회전의 방향 변화를 생각하면서 잘 구현해 줍시다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
int rot[4040404], flip[4040404], l_rot[4040404], l_flip[4040404], n, m;
 
void prop(int now, int l, int r){
	if(!l_rot[now]) return;
	flip[now] = (l_flip[now]&1)*(r-l+1)%2;
	rot[now] = l_rot[now]*(l_flip[now]?(r-l+1)%2:r-l+1);
	l_rot[now<<1] = l_rot[now<<1|1] = l_rot[now];
	l_flip[now<<1] = l_flip[now<<1|1] = l_flip[now];
	l_rot[now] = l_flip[now] = 0;
	return;
}
 
void upd(int now, int l, int r, int L, int R, int ro, int fl){
	prop(now, l, r);
	if(l > r || L > r || l > R) return;
	if(L <= l && r <= R){
		l_rot[now] = ro;
		l_flip[now] = fl;
		prop(now, l, r);
		return;
	}
	upd(now<<1, l, mid, L, R, ro, fl);
	upd(now<<1|1, mid+1, r, L, R, ro, fl);
	rot[now] = (flip[now<<1|1]&1) ? rot[now<<1|1]-rot[now<<1] : rot[now<<1|1]+rot[now<<1];
	flip[now] = (flip[now<<1]+flip[now<<1|1])%2;
	return;
}
 
void upd(int L, int R, char c){
	upd(1, 1, m, L, R, (c=='R' || c=='H') ? 1:-1, (c=='H'||c=='V'));
	return;
}
 
char board[1234][1234];
 
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++){
		string str; cin >> str;
		for(int j = 1; j <= n; j++) board[i][j] = str[j-1];
	}
	cin >> m; string command; cin >> command;
	for(int i = 1; i <= m; i++) upd(i, i, command[i-1]);
	int Q; cin >> Q; while(Q--){
		int q; cin >> q;
		if(q == 2){
			int L, R; char c; cin >> L >> R >> c;
			upd(L, R, c);
		}
		else{
			int r, c, tmp; cin >> r >> c;
			int ro = (4+rot[1]%4)%4, fl = flip[1]%2;
			switch(ro){
				case 0:
					break;
				case 1:
					tmp = r;
					r = n+1-c;
					c = tmp;
					break;
				case 2:
					r = n+1-r;
					c = n+1-c;
					break;
				case 3:
					tmp = c;
					c = n+1-r;
					r = tmp;
					break;
			}
			if(fl) swap(r, c);
			cout << board[r][c] << '\n';
		}
	}
}