레이지 프로퍼게이션2 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 = .. 2020. 5. 21. 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 1.. 2020. 5. 21. 이전 1 다음