BOJ 32183 바이러스

문제 링크입니다.

봇치야 이게 무슨 표현식이니

이상한 정규 표현식이 주어졌습니다. 문자열의 뒤에 0 또는 1을 추가하는 행위를 상태 전이로 생각하고, 상태 수를 줄이기 위해 문자열을 정규 표현식 위에서의 패턴에 따라 분류합니다. 패턴의 분류 방법은 여러 가지일 수 있습니다. 아래는 제가 분류한 패턴과 0 또는 1을 뒤에 추가했을 때의 상태 전이를 그래프로 나타낸 그림입니다.

자구에 올리기

각 비트는 하나의 상태를 다른 상태로 옮기는 함수입니다. 여러 개의 비트가 연속해 있는 경우 왼쪽의 비트부터 순서대로 처리하면 결국 하나의 비트와 마찬가지로 하나의 상태를 다른 상태로 옮기는 함수로 볼 수 있습니다. 함수의 합성은 결합법칙이 성립하므로, 세그먼트 트리를 이용해 구간 [l, r]에 대응하는 함수를 $\mathcal{O}(\lg N)$에 얻을 수 있습니다.

구간의 비트를 변경하는 업데이트를 처리하는 것은 쿼리로 들어올 수 있는 네 종류의 조합 (00, 01, 10, 11) 모두에 대한 업데이트 후 결과를 노드에 저장해서 할 수 있습니다. 실제로 구하고자 하는 전체 비트열 처리 후의 상태는 루트 노드의 01 업데이트 후 결과로 얻어낼 수 있습니다.

느리게 갱신되는 세그먼트 트리를 이용해 구간 업데이트를 처리하면, 총 시간 복잡도는 $\mathcal{O}(N \lg N)$입니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;

const array<bool, 9> judge = {0,0,0,0,0,1,1,1,0};
const array<int, 9> f0 = {1,1,8,5,6,1,1,6,8};
const array<int, 9> f1 = {2,3,4,8,8,2,7,7,8};
string s; int n, q;

struct Node{
	array<int, 9> f[4];
};

Node tree[404040]; int lazy[404040];

Node merge(Node& l, Node& r){
	Node ret;
	for(int bit = 0; bit < 4; bit++){
		for(int x = 0; x < 9; x++) ret.f[bit][x] = r.f[bit][l.f[bit][x]];
	}
	return ret;
}

void prop(int now, int l, int r){
	if(lazy[now] == 1) return;
	if(l != r){
		if(lazy[now] == 0 || lazy[now] == 3) lazy[now<<1] = lazy[now<<1|1] = lazy[now];
		else if(lazy[now] == 2){
			lazy[now<<1] = 3-lazy[now<<1];
			lazy[now<<1|1] = 3-lazy[now<<1|1];
		}
	}
	if(lazy[now] == 0){
		tree[now].f[1] = tree[now].f[0];
		tree[now].f[2] = tree[now].f[3];
	}
	if(lazy[now] == 3){
		tree[now].f[2] = tree[now].f[0];
		tree[now].f[1] = tree[now].f[3];
	}
	if(lazy[now] == 2){
		swap(tree[now].f[1], tree[now].f[2]);
	}
	lazy[now] = 1;
	return;
}

void upd(int now, int l, int r, int L, int R, int op){
	prop(now, l, r);
	if(l > R || L > r) return;
	if(L <= l && r <= R){
		lazy[now] = op;
		prop(now, l, r);
		return;
	}
	upd(now<<1, l, mid, L, R, op);
	upd(now<<1|1, mid+1, r, L, R, op);
	tree[now] = merge(tree[now<<1], tree[now<<1|1]);
}

void qry(){
	prop(1, 0, n-1);
	cout << (judge[tree[1].f[1][0]] ? "YES\n" : "NO\n");
}

void init(int now, int l, int r){
	lazy[now] = 1;
	if(l == r){
		if(s[l] == '0'){
			tree[now].f[0] = tree[now].f[1] = f0;
			tree[now].f[2] = tree[now].f[3] = f1;
		}
		else{
			tree[now].f[0] = tree[now].f[2] = f0;
			tree[now].f[1] = tree[now].f[3] = f1;
		}
		return;
	}
	init(now<<1, l, mid); init(now<<1|1, mid+1, r);
	tree[now] = merge(tree[now<<1], tree[now<<1|1]);
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> s >> q;
	init(1, 0, n-1); qry();
	while(q--){
		string op; int L, R; cin >> op >> L >> R;
		int o = (op[0]-'0')*2+(op[1]-'0');
		upd(1, 0, n-1, L, R, o); qry();
	}
}