ett4 BOJ 15899 - 트리의 색깔 (ett, 머지소트트리) https://www.acmicpc.net/problem/15899 기록용 최대 2e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 최대 2e5의 값(색)을 하나씩 갖는다. 다음 쿼리를 처리하자 v c : 정점v를 루트로 하는 서브트리에서 값이 c이하인 정점의 수 서브트리를 구간트리로 처리할 수 있는지? 할 수 있다면 머지소트트리가 가장 적합함 (update쿼리가 없어서 가능) ett번호를 붙여주고 머지소트트리 일반적인 풀이 쓰면 된다. const int MAX = 2e5 + 4; const int MOD = 1e9 + 7; const int SMAX = (1 = 1; i--) { seg[i] = seg[i * 2 + 1]; seg[i].insert(seg[i].end(), seg[i * 2].begi.. 2020. 6. 2. BOJ 13309 - 트리 (레이지, ett, 트리) https://www.acmicpc.net/problem/13309 트리+세그 공부하게 된 계기 최대 2e5개의 정점을 갖는 루트가 1인 트리가 주어진다. 다음 쿼리를 처리하라 x y 1 : 정점x,y를 잇는 경로가 있다면 "YES"출력 후 x와 x의부모를 잇는 간선 제거 없다면 "NO" 출력 후 y와 y의 부모를 잇는 간선 제거 x y 0 : 정점x,y를 잇는 경로가 있다면 "YES", 없다면 "NO" 출력 정점 u와 p[u]의 간선을 끊는 것을 한 쪽의 색을 칠한다고 생각해보면 다음과 같다. u와 A의 크기가 더 작을 경우 u쪽을 새로 칠하고 p[u]와 B의 크기가 더 작을 경우 p[u]쪽의 색을 새로 칠한다면 amortized log시간에 쿼리를 처리할 수 있다. (점점 색칠할 영역이 반절로 줄어듦.. 2020. 5. 22. 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 다음
