hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

A. [23238] Best Student (Diamond V) 더보기 의도한 태그: Mo's Algorithm + Square Root Decomposition 문제를 간단히 해석하자면, \( [L, R] \) 구간에서 가장 많이 등장한 학생을 찾는 문제가 됩니다. 그러니 Mo's를 사용하면 간단히 해결할 수 있겠죠. 그런데, 가장 많이 등장한 학생을 찾을 때 "등장 횟수"를 Segment Tree 같은 걸로 저장시키면 시간복잡도에 log가 붙으면서 TLE가 나게 됩니다. 그러니, "등장 횟수"의 개수를 Square Root Decomposition으로 관리해주면 됩니다. Square Root Decomposition의 시간 복잡도는 Mo's와 독립적으로 계산되므로, 합하면 \( O(Q \sqrt(N)..

다룬 태그들 더보기 구간 나눠서 처리하기 (A) Square Root Decomposition (BC) Mo's Algorithm (DEF) A. [20537] Gap (Platinum III) 더보기 Subtask 1은 간단히 해결할 수 있습니다. \( a = 0, b = 10^{18} \)으로 놓은 뒤, \( f(a, b) \)를 호출하면 가장 작은 수와 가장 큰 수를 알 수 있게 됩니다. 그럼 그 가장 작은 수와 가장 큰 수를 제외하고 남은 \( N-2 \)개의 수에 대해 재귀적으로 탐색해주면 됩니다. 이는 \( a = mn+1, b = mx-1 \)로 범위를 조정시키면 됩니다. 그럼 배열의 모든 원소를 알 수 있게 되므로, 문제를 간단히 해결할 수 있습니다. Subtask 2는 아래와 같이 해결할..

다룬 태그 더보기 Trie (ABCDEF) A. [14725] 개미굴 (Gold III) 더보기 트라이를 구축하는 문제입니다. 차이점이라면, 문자열에서 하나의 글자를 들고 오는 대신 문자열의 배열에서 하나의 문자열을 꺼내서 쓰는 정도의 차이가 있습니다. (사실 이 문제는 트라이 없이도 풀 수 있습니다. 그래서 Gold III이라는 낮은 난이도를 받은 거고요.) struct Node{ map nxt; }; vector trie; void psh(int ni, vector& v, int vi){ int vl = v.size(); if (vi == vl){ return; } if (trie[ni].nxt.count(v[vi]) == 0){ trie[ni].nxt[ v[vi] ] = trie.size(); tr..

다뤄본 태그 더보기 Euler Tour Technique (ABCDE) A. [2820] 자동차 공장 (Platinum III) 더보기 Subtree Add Update와 Point Query입니다. Euler Tour Technique를 사용하면 우리가 잘 풀 수 있는 형태인 Range Add Update와 Point Query로 바꿀 수 있습니다. 아래 쓰인 코드는 Difference 배열을 사용해서 Range Update / Point Query를 Point Update / Range Query로 바꾼 방식입니다. 이에 관해 간단히 설명해보자면 \( D_{i} = A_{i} - A_{i-1} \)을 정의한다면, \( A_{i} = \sum_{j=1}^{i} D_{i} \)가 됩니다. 그럼, \( D..

다룬 태그들 더보기 Sparse Table (ABC) Lowest Common Ancestor (DEFG) A. [17435] 합성함수와 쿼리 (Gold I) 더보기 \( f^N(x) \)는 \( f^1(x), f^2(x), f^4(x), \ldots, f^{2^k}(x) \)의 적절한 합성으로 만들 수 있습니다. 그러니, Exponentiation by Squaring 하듯이 전처리를 돌리고 쿼리를 처리해주면 됩니다. const int B = 20; int spr[22][200020]; void Main(){ int n; cin >> n; for (int i = 1; i > spr[0][i]; } for (int b = 1; b q; while (q--){ int k, x; cin >> k >> x; ..

A. [20039] Coronavirus Trend (Platinum II) 더보기 의도한 태그: Segment Tree + DP 우선, 두 수의 차이를 계산해야 하니 길이가 \( N - 1 \) 차이 배열 \( D_{i} = A_{i+1} - A_{i} \)을 만들어볼 수 있습니다. 이를 통해 문제를 재정의하면, Difference 배열에서 값을 적절히 합쳐서 고립된 +, -가 없도록 만드는 문제가 됩니다. (문제의 조건에 의해, 0은 고려하지 않아도 됩니다.) 이제, DP로 이 문제를 풀어봅시다. \( DP_{i, s, c} := A_{[1, i]} \)에 대해, 마지막 수의 부호가 \( s \)이며, 이 부호가 현재 \( c \)회 연속으로 나오게 하기 위해 필요한 합치기의 최소 횟수 문제 특성상,..

다룬 태그들 더보기 세그먼트 트리의 수열 직접 정의해보기 (ABCD) 2-Dimensional Segment Tree (EF) Kth Segment Tree (GH) Merge Sort Tree (IJ) Continuous Sum Segment Tree (KL) A. [10090] Counting Inversions (Platinum V) 더보기 Inversion을 좀 더 명확히 정의하면, \( i A_{j} \)인 \( (i, j) \) 쌍을 의미합니다. 그럼 우리가 \( j \)를 기준으로 돌리면서 앞에 나온 값들 중 \( A_{j} \)보다 더 큰 값의 개수를 찾아주면 됩니다. 그래서 \( B_{x} := \) \( A_{j} = x \)인 \( j < i \)..

다룬 태그 더보기 Segment Tree (ABCDEFG) Segment Tree with Lazy Propagation (HIJKLM) A. [2042] 구간 합 구하기 (Gold I) 더보기 세그먼트 트리의 기본형 문제입니다. 어떤 원소의 업데이트와, 구간의 합을 처리해주면 됩니다. const int N = 1048576; ll seg[2097160]; void upd(int pos, ll val){ pos += N-1; seg[pos] = val; pos >>= 1; while (pos){ seg[pos] = seg[pos= 1; ed >>= 1; } return res; } void Main(){ int n, m, k; cin >> n >> m >> k; int q = m+k; for (int i..