백준/세그먼트 트리 (27) 썸네일형 리스트형 [ICPC] 백준 5012 - 불만 정렬 https://www.acmicpc.net/problem/5012 문제를 해결하기 위해 펜윅 트리에 다음 정보를 관리할 것이다. 현재 순회 중인 index에 해당하는 값 val 이상의 값이 출현하는 횟수 그러면 val을 pivot으로 할 때 구간은 다음과 같이 표현될 수 있다. [val보다 작은 index에서 val 이상의 값이 나타나는 횟수), val, (val 보다 큰 index에서 val 이상의 값이 나타나는 횟수] 이렇게 되면 왼쪽 구간에서 큰 수를 선택하는 경우와 오른쪽 구간에서 작은 수를 선택하는 경우를 곱셈법칙으로 계산하여 왼쪽 구간의 값 * (오른쪽 원소의 갯수 - 오른쪽 구간의 값)를 각 pivot마다 더해주어 답을 구할 수 있다. 하지만 이렇게 하면 왼쪽 구간에서 val보다 큰 값이 있.. [COCI] 백준 3006 - 터보 소트 https://www.acmicpc.net/problem/3006 Intro 문제를 잘 읽어보면 칵테일 정렬과 비슷한 논리로 진행됨을 이해할 수 있다. 그렇다고 진짜 칵테일 정렬을 수행하면 $O(N^{2})$의 시간복잡도로 참사가 일어날 것이 분명하다. 그렇다면 우리는 이 문제를 어떻게 풀어야 할까? 아이디어 위 gif 이미지를 보면 배열의 양 끝이 정렬되는 것을 알 수 있다. 그리고 우리는 정렬된 부분을 다시 건드리지 않는 것이 최적임을 너무나도 잘 알고있다. 이를 바꿔서 생각하면 터보 소트의 동작이 수행될 때마다 나머지 원소들이 정렬을 위해 이동해야 할 최대 거리가 1씩 줄어든다는 것이다. 그렇다면 정렬이 진행되는 과정에서 각 원소가 이동해야 하는 거리를 효율적으로 계산하면 괜찮을 거라는 생각을 할 .. [ICPC] 백준 2104 - 부분배열 고르기 https://www.acmicpc.net/problem/2104 문제에서 요구하는 사항을 처리하기 위해서는 두 개의 세그먼트 트리가 필요하다. 하나는 구간합을 저장하는 트리, 나머지는 구간의 최솟값의 index를 저장하는 트리이다. 최솟값도 아니고 그 index를 저장하는 이유는 다음 전략을 따르기 때문이다. 1. 특정 구간 x의 연산 결과를 구한다. 2. x의 최소 원소 xval가 없는 구간은 xval보다 큰 수를 곱할 것이 자명하다. 3. 그렇다면 xval이 빠진 구간의 연산 결과는 구간 x의 연산 결과보다 커질 수 있다는 기대를 가질 수 있다.(입력은 전부 1 이상의 정수이므로 더하는 것보다 곱하는게 더 영향이 크다는 사실을 상기하라.) 4. 그러므로 우리는 xval를 pivot으로 하여 구간을 .. [ICPC] 백준 9345 - 디지털 비디오 디스크 https://www.acmicpc.net/problem/9345 아이디어 고객이 l번부터 r번까지의 DVD를 원할 때 이들의 index 최솟값과 최댓값은 l과 r이다. 그러면 도중에 DVD가 바뀌었다 하더라도 l번부터 r번까지 DVD의 index 최솟값과 최댓값이 l과 r이면 해당 구간에 동일한 내용물이 들어있음을 이해할 수 있다. 왜냐하면 DVD 집합의 크기가 변하는 것이 아니기 때문에 index의 경계를 살펴보면 원하는 원소들이 속해있는지 속하지 않았는지 판단할 수 있기 때문이다. 그러면 세그먼트 트리를 통해 특정 구간에서 index의 최소와 최대를 저장하여 질의를 처리하는 방법을 생각해 볼 수 있다. 구현 문제를 풀기 위해 다음 역할을 하는 배열을 사용한다. ar[선반 번호] = DVD 번호 초기.. 백준 13544 - 수열과 쿼리 3 https://www.acmicpc.net/problem/13544 특정 구간에서 어떤 원소를 상대로 질의를 처리하는 것은 머지 소트 트리를 이용하여 할 수 있다. 머지 소트 트리를 구현한 후 문제에서 요구하는 대로 질의를 처리한 결과를 출력하면 AC를 받을 수 있다. 마지막으로 출력한 결과와 XOR 연산을 해줘야 하는 것을 잊지 말자. # XOR를 해주는 이유는 오프라인 쿼리를 사용할 수 없게 하기 위함이라고 한다. 전체 코드 더보기 #include using namespace std; vector tree[400000]; int ar[100001]; int mid(int s, int e) { return s + (e - s) / 2; } void init(int node, int start, int .. 이전 1 2 3 4 5 6 다음
