알고리즘/백준 & swacademy108 BOJ 15977 - 조화로운 행렬 (분할정복, 세그트리) https://www.acmicpc.net/problem/15977 정해는 다차원 세그트리나 이분탐색+set이다. https://codeforces.com/blog/entry/43319 koosaga님의 아이디어를 구현. m=2인 경우 정렬 후 LIS m=3인 경우 정렬 후 LIS on pair (x,y값이 모두 증가하는 형태) 링크의 설명이 너무 명료하므로 큰 그림은 생략. [m+1,e] 범위의 dp를 [s,m] 범위의 dp 값으로 초기화 하는 과정만 기록 세그트리는 y를 인덱스로 하고 dp값을 값으로 갖는다. 1. 하나의 벡터에 {x,y,idx}를 [s,e]범위 모두 넣어준 후 x값 기준으로 정렬한다. 2. idx가 md이하인 경우 세그트리를 업데이트 해준다. 3. idx가 md초과인 경우 세그트리의.. 2020. 5. 30. 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 2 3 4 5 6 ··· 27 다음
