백준/세그먼트 트리 (27) 썸네일형 리스트형 백준 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 https://www.acmicpc.net/problem/17353 사전 지식 imos법을 알면 풀이를 쉽게 이해할 수 있다. 이 포스트에서는 imos법을 알고 있다는 가정 하에 설명하도록 한다. 공차가 1인 등차 수열 이 문제는 공차가 1인 등차수열을 구간에 더하면서 포인트 쿼리를 수행한다. 여기서 포인트 쿼리를 구간 쿼리로 바꿔보자. 점 x에 떨어진 별의 개수가 아닌 구간 [1, x]의 합을 구하는 쿼리로 바꾼다. 왜 이렇게 쿼리를 바꾸냐면 쿼리 1을 스위핑 덧셈 문제로 바꾸기 위함이다. 얘를 들어 다음 배열을 살펴보자. 1 2 3 4 5 이 배열의 원소들 $a_{1}, a_{2},... $을 $imos(i) - imos(0)$의 형태로 구하려면 어떻게 할까? 1 1 1 1 1 -5 이렇게 배열을 구.. [ICPC] 백준 23245 - Similarity https://www.acmicpc.net/problem/23245 대회 당시 내가 푼 문제임에도 불구하고 귀찮다는 이유로 안 쓰고 있었는데 다른 글들을 둘러보니 나와는 다른 방향으로 푼 거 같아 작성하고자 한다. 사실 여기서 적을 것은 별로 없다. 주어진 수열 쌍을 적절히 오름차순으로 정렬하고 좌표 압축을 수행하면 아래 문제와 조건이 동일해진다. https://www.acmicpc.net/problem/17409 17409번: 증가 수열의 개수 첫째 줄에 N, K가 주어진다. 둘째 줄에 수열 A1, A2, ..., AN이 주어진다. www.acmicpc.net 그러면 위 문제에서 k가 3인 버전으로 생각하고 세그먼트 트리로 LIS 카운팅 DP를 수행하면 된다. 자세한 풀이는 여기를 참고하라. 그런데 다.. 백준 1572 - 중앙값 https://www.acmicpc.net/problem/1572 전형적인 세그먼트 트리로 k번째 수를 찾는 쿼리를 이용하는 문제이다. 하지만 그 구현은 너무나도 귀찮다. C++을 사용하고 있다면 pbds를 이용해 간단하게 풀 수 있다. find_by_order와 order_by_key를 잘 이용하자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #pragma GCC target("sse.. 백준 14287 - 회사 문화 3 참고 오일러 투어에 대해 모르면 여기를 먼저 보고 오자. 풀이 회사 문화 2와는 달리 더하는 방향이 반대이다. 어떻게 처리할 수 있을까? 일단 예제의 그래프를 그려보자. 여기서 정점 3에 3의 값을 더하면 1까지 3씩 더해야 한다. 하지만 단순히 간선 방향을 거꾸로만 하면 정점이 계속 중복 계산돼서 시간 초과 판정을 받고 방문 처리를 하면 사장까지 올라갈 수 없는 경로가 생겨 제대로 된 답을 계산할 수 없다. 이렇게 생각하면 무언가 떠올릴 수 있다. 부하의 칭찬을 나중에 한꺼번에 떠안자. 무슨 말이고 하면 정점 4에 5를 더하고 정점 2에 2를 더한 상태에서 정점 2의 칭찬도를 얻으려면 다음과 같이 할 수 있다. 아래로 값을 더하지 말고 2와 4의 값만 변경한 다음 2의 오일러 투어 구간 [2, 5]의 .. 백준 17408 - 수열과 쿼리 24 https://www.acmicpc.net/problem/17408 값을 바꾸는 것은 극히 기본적인 세그먼트 트리의 연산이지만 구간 내 두 원소의 합 중 최댓값을 가져오는 연산이 쉽지 않을 수 있다. 다시 생각하면 구간 내 두 원소의 합 중 최댓값은 구간 내에서 가장 큰 값 2개를 가지고 있는 것과 동일하며 해당 쿼리는 구간 내에서 가장 큰 2개의 값을 보존하는 문제로 바뀐다. 가장 큰 2개의 값을 보관하기 위해 C++ 기준 pair를 관리하는 세그먼트 트리를 구성하자. 그러면 왼쪽 절반 L에서 가장 큰 두 값을 저장하는 pair와 오른쪽 절반 R에서 가장 큰 두 값을 저장하는 pair를 가지고 다음 그림처럼 구간을 갱신할 수 있다. 위 그림처럼 가장 큰 두 개의 값을 들고 다니면 된다. 아는 사람은 짐.. 이전 1 2 3 4 ··· 6 다음
