BOJ 14268,7 - 내리 칭찬2, 3 (레이지, 트리, ett)

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

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

원래 버전은 내리갈굼이었는데 순화됐다.

 

 

(내리칭찬3)

 

<문제설명>

최대 1e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 칭찬수치를 갖는다. 다음 두가지 쿼리에 대해 처리하라

1. x, w : x정점의 칭찬수치를 w만큼 더한다.

2. x : x정점의 후손들의 칭찬수치를 모두 더하여 출력

 

<풀이>

트리를 dfs하여 정점(x)마다 방문순서(l[x])를 기록해둔다면, 정점x를 루트로하는 서브트리는 [l[x], l[x]+#children[x]]의 구간을 갖는다.

 

l[x],r[x]사이의 칭찬수치값을 모두 더해준다.

 

<코드>

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

int n, qq, l[MAX], r[MAX], seg[SMAX];
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 update(int i, int x) {
	i += SMAX / 2;
	seg[i] += x;
	while (i > 1) {
		i /= 2;
		seg[i] = seg[i * 2] + seg[i * 2 + 1];
	}
}

int val(int s, int e, int i, int ns, int 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 >> qq;
	for (int i = 1, x; i <= n; i++) {
		cin >> x; if (i == 1) continue;
		g[x].push_back(i);
	}
	dfs(1);

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

 

 

---

(내리칭찬2)

 

<문제설명>

최대 1e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 칭찬수치를 갖는다. 다음 두가지 쿼리에 대해 처리하라

1. x, w : x를 루트로하는 서브트리 전체에 칭찬수치를 w만큼 더한다

2. x : 정점 x의 칭찬수치를 출력

 

<풀이>

트리를 dfs하여 정점(x)마다 방문순서(l[x])를 기록해둔다면, 정점x를 루트로하는 서브트리는 [l[x], l[x]+#children[x]]의 구간을 갖는다.

 

이를 이용하여 구간 update를 해주면 된다.

 

주의 : 2번쿼리가 포인트 쿼리라고 seg[x+SMAX/2]를 그대로 출력하면 틀린다. lazy값을 적용하기 전의 상태일 수 있으므로 각 단계마다 propagate를 해줘야 한다. 따라서 포인트쿼리도 재귀함수를 사용하여 구해줘야 한다.

 

<코드>

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

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

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

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

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

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

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

	int md = (ns + ne) / 2;
	update(s, e, k, node * 2, ns, md);
	update(s, e, k, node * 2 + 1, md + 1, ne);
	seg[node] += seg[node * 2] + seg[node * 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 node, int ns, int ne) {
	propagate(node, ns, ne);
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return seg[node];
	int md = (ns + ne) / 2;
	return val(s, e, node * 2, ns, md) + val(s, e, node * 2 + 1, md + 1, ne);
}
int val(int x) {
	return val(x, x, 1, 0, SMAX / 2 - 1);
}

int main() {
	FAST; cin >> n >> qq;
	for (int i = 1, x; i <= n; i++) {
		cin >> x; if (i == 1) continue;
		g[x].push_back(i);
	}
	dfs(1);

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

 

<생각>

펜윅트리로 짜면 lazy배열 사용하지 않고 구현할 수 있다.