알고리즘225 BOJ 3392 - 화성지도 (세그트리 응용) https://www.acmicpc.net/problem/3392 코드는 다음 블로그의 코드를 많이 참조했습니다. https://jason9319.tistory.com/58 일반적인 세그트리의 형태를 따르지 않고, 세그먼트트리의 구조를 이용하여 풀 수 있는 문제. 좌표가 최대 30000인 2차원 평면 상에 최대 1e4개의 직사각형이 주어질 때, 직사각형들이 이루는 영역의 크기를 구하라 x좌표가 증가하는 순서대로 막대기들을 볼 때, "이전 x좌표와의 차 dx"와 "y좌표들의 psum이 1이상인 곳의 개수"를 곱해나가면 된다. 지금 막대기가 [y1,y2)일 떄 이 막대기가 시작 막대기인 경우 해당구간을 모두 +1, 끝 막대기인 경우 해당구간을 모두 -1해주며 배열을 유지해 나간다고 생각해야 한다. 이걸 la.. 2020. 6. 6. 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 2912 - 백설공주와 난쟁이 (머지소트트리, 구간 과반수) https://www.acmicpc.net/problem/2912 한 구간의 원소중 무작위로 하나 골랐을 때 그 원소가 그 구간의 과반수일 확률은 (1/2) 이상이다. 이를 이용해서, 한 쿼리당 20번씩 무작위로 골라서 확률을 높이는 방법도 존재한다. ~~(1e6-1)/1e6의 쿼리개수 승 = 99.00++% 최대 길이 3e5의 배열이 주어진다. 모자 색의 가짓수는 1e4 이하이다. 다음 쿼리를 처리하자 s, e : 구간[s,e]의 과반수값이 존재하면 "yes 과반수값", 존재하지 않으면 "no" 출력 vector c[i] : i색상 모자를 갖는 인덱스들 (오름차순) 구간[s,e] 사이에 i색상 모자가 몇 개 들어있는지는 위 벡터에서 이분탐색하여 알 수 있다. 머지소트트리 상에서 해당 구간에 포함되는 블.. 2020. 6. 2. 머지소트 트리 1. update가 이뤄지지 않으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리 2. 포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 존재성과 그 최소값을 물어보는 쿼리 위 1,2번 경우 기존 세그트리를 약간만 변형하여 머지소트 트리를 만들어 풀 수 있다. 1번은 각 세그 노드마다 벡터를, 2번은 set을 쓴다면 이분탐색으로 쉽게 풀 수 있다. 3. 포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리 3번 경우, 세그트리에 splay tree나 treap이나 데카르트트리따위를 넣어 해결할 수 있다고 한다. ->구현 매우 어려움. gcc 내장 트리를 사용한다면 쉬워질 수 있을 것 같다. https://www.acmicpc.net/p.. 2020. 6. 2. 이전 1 2 3 4 5 6 7 ··· 57 다음