BOJ 18437 - 회사문화 5 (레이지, ett, 트리)

https://www.acmicpc.net/problem/18437

ett+세그(구간업뎃) 

 

<문제설명>

최대 1e5개의 정점으로 이뤄진 트리가 주어진다. 각 정점마다 꺼짐,켜짐 두 상태를 지닐 때, 다음 쿼리에 답하라

(초기엔 모두 켜짐)

1 x : x를 조상으로 둔 모든 정점 켬

2 x : x를 조상으로 둔 모든 정점 끔

3 x : x를 제외한 후손 중 켜진 정점들의 수

 

<풀이>

ett+레이지 하면된다. 세그엔 구간합을 담고, 쿼리마다 x서브트리 모두 켜기/끄기만 유의해서 짜주면 된다.

 

모두 켜는 연산의 경우 seg[i] 는 해당 구간의 크기 값을 담고, 끄는 경우엔 0을 담으면 된다.

 

레이지 배열엔 적용할 연산을 담는다고 생각하면 된다.

 

<코드>

const int MAX = 1e5 + 4;
const int SMAX = (1 << 18);

int seg[SMAX], lazy[SMAX], n, qq, l[MAX], r[MAX];
vector<int> g[MAX];

int counter;
void dfs(int u) {
	l[u] = counter++;
	for (int v : g[u]) dfs(v);
	r[u] = counter - 1;
}

void construct() {
	for (int i = SMAX / 2 - 1; i >= 1; i--)
		seg[i] = seg[i * 2] + seg[i * 2 + 1];
}

void propagate(int i, int ns, int ne) {
	if (lazy[i] == 0) return;

	if (i < SMAX / 2) {
		lazy[i * 2] = lazy[i * 2 + 1] = lazy[i];
	}
	seg[i] = lazy[i] == 1 ? (ne - ns + 1) : 0;
	lazy[i] = 0;
}

void update(int s, int e, int k, int i, int ns, int ne) {
	propagate(i, ns, ne);

	if (e < ns || ne < s) return;
	if (s <= ns && ne <= e) {
		lazy[i] = k;
		propagate(i, ns, ne);
		return;
	}

	int md = (ns + ne) / 2;
	update(s, e, k, i * 2, ns, md);
	update(s, e, k, i * 2 + 1, md + 1, ne);
	seg[i] = seg[i * 2] + seg[i * 2 + 1];
}
void update(int s, int e, int k) {
	return update(s, e, k, 1, 0, SMAX / 2 - 1);
}

int val(int s, int e, int i, int ns, int ne) {
	propagate(i, ns, ne);

	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return seg[i];
	int md = (ns + ne) / 2;
	return val(s, e, i * 2, ns, md) + val(s, e, i * 2 + 1, md + 1, ne);
}
int val(int s, int e) {
	return val(s, e, 1, 0, SMAX / 2 - 1);
}

int main() {
	FAST; cin >> n;
	for (int i = 1, x; i <= n; i++) {
		cin >> x; g[x].push_back(i);
		seg[i+SMAX/2] = 1;
	}
	construct();
	dfs(0);

	cin >> qq;
	for (int i = 0, opt, x; i < qq; i++) {
		cin >> opt >> x;
		if(opt==3) cout << val(l[x] + 1, r[x]) << '\n';
		if (l[x] == r[x]) continue;

		if (opt == 1) update(l[x]+1, r[x], 1);
		if (opt == 2) update(l[x]+1, r[x], -1);
	}
}