세그먼트트리5 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. BOJ 14463 - 소가 길을 건너간 이유 9 (세그트리, 라인스위핑) https://www.acmicpc.net/problem/14463 distinct한 좌표를 갖는 교차하는 선분쌍의 '개수' nlogn에 구하기 참고: n^2에 모든 교차하는 선분쌍을 하나하나 들여다 보는 로직 https://suuntree.tistory.com/112 선분i를 처음부터 순차로 보면서, 선분 i의 범위가 [lo,hi]라면, hi를 세그먼트트리에서 1 올리는 update를 해준다. 그러면 0~i-1번 선분과 선분 i가 교차하는 쌍의 개수는 psum[i끝점] - psum[i시작점]이다. 다시말해서, 0~i-1번 선분 중에 선분 i[lo,hi]와 교차하는 선분의 개수는, 끝나는 점이 [lo,hi]에 속하는 선분의 개수이다. (선분i에 포함되는 선분은 i+1이후이므로 신경쓰지 않는다.) cons.. 2020. 2. 29. BOJ 14170 - Counting Haybales (usaco silver, 차원압축, 세그먼트트리) https://www.acmicpc.net/problem/14170 분류를 차원압축과 세그먼트트리로 하긴 했지만 훨씬 쉽게 풀 수는 있다. 하지만, 차원압축에 익숙해지기 위한 예제로 사용하면 좋을 것 같다. #include #include #include #include using namespace std; const int MAX = 1 = 1; i--) arr[i] = arr[i * 2] + arr[i * 2 + 1]; } int sum(int s, int e, int node, int ns, int ne) { if (e > q; int x[100000], hsize=0; set xSet; unordered_map xHash; //입력 및.. 2019. 10. 3. lazy propagation - 세그먼트 트리 확장 코드의 상당부분은 kks227(라이)님의 코드를 참고했음을 밝힙니다. 기본문제 https://www.acmicpc.net/problem/10999 https://www.acmicpc.net/problem/12844 https://www.acmicpc.net/problem/1395 구간 합을 빠르게 구하기 위해서 prefix 배열을 이용 -> update 등의 다수의 쿼리가 발생했을 때도 구간 합을 빠르게 구하기 위해서 segment tree 사용 -> 구간 update 등 다수의 쿼리가 발생했을 때 구간 합을 빠르게 구하기 위해 lazy배열과 propagation 사용 필요한 것: segment tree, lazy 배열 propagate(node, ns, ne) : add나 val 함수에서의 node에 .. 2019. 9. 18. 이전 1 2 다음