seojin0305 PS 블로그

시간복잡도 $O(L + NlogL), L = log(max(S_0, S_1))$ 풀이 1번째 test case인 (21, 12)를 관찰해보자. 21, 12, 9, 3, 6, 3, 3, 0, 3, 3, 0, ... 보이는 것과 같이 3, 3, 0이 반복됨을 관측할 수 있다. 이로부터 같은 수가 연속해서 나오면 그 뒤는 $a, a, 0$이 반복됨을 알 수 있다. 그러나 $(10^{18}, 1)$와 같은 경우 같은 수가 연속한 경우까지 너무 오래 걸린다. 만약 $(a, b)$에서 $a \gg b$라면, $a, b, a-b, a-2b, b$까지는 자명함을 알 수 있다. 즉 $(a, b)$에서 $(a-2b, b)$, 나아가 $(a-2kb, b)$까지 확장시킬 수 있는 것이다. 정리해보자면, $(a, b)$에서 i..

알고리즘 lazy_segtree, coor_comp ( map ) 시간복잡도 $O(QlogQ)$ 풀이 문제 조건 상 x좌표가 증가할수록 색칠되어 있는 칸의 수는 감소한다. 따라서 각 쿼리를 $q_x, q_y$라 하면 (색칠되어 있는 칸의 수가 $q_y$ 이상인 가장 작은 x좌표 ~ $q_x$) 구간을 $q_y$로 업데이트 후 전체 합을 구해주면 된다. 이 때 x좌표 범위가 $10^9$까지이므로 좌표압축을 해줘야 한다. 구간 update를 진행해야 하므로 {x좌표 두께를 고려한 넓이, max, min}에 대한 lazy seg로 구현하였다. 기존 lazy seg의 update에서 추가적으로 구간 min이 update할 값 이상이면 return, update 범위 내에 있으며 구간 max가 update할 값 ..

알고리즘 coor_comp, segtree 시간복잡도 $O((M+N)logN)$ 풀이 우선 주어진 모든 좌표(고기의 시작/끝 좌표, 꼬치의 좌표)를 기준으로 좌표 압축을 진행한다. 가능한 값은 최대 $2(N+M)$ 개이다. 이제 각 쿼리별로 진행해보자. 한 꼬치에 꽂힐 수 있는 고기의 종류를 모두 알아내면 쉽게 정답을 구할 수 있다. 우선 고기를 시작 좌표 기준 오름차순으로 정렬한다. 이 경우 각 꼬치에 대해 1번 고기부터 특정 고기까지만 꽂힐 후보가 됨이 보장된다. 이제 고기 후보들 중 실제로 꼬치에 꽂히는 고기를 찾아보자. {끝 좌표의 최댓값, 해당 고기}에 대한 segtree를 만들면, 위에서의 고기 후보 구간 내 끝 좌표가 가장 큰 고기를 알 수 있게 된다. 끝 좌표가 가장 큰 고기도 꼬치에 꽂히..

알고리즘 (segtree) 시간복잡도 $O(NlogN)$ 풀이 $g(K)$, 즉 배열 중 $1\sim K$만을 고려하는 경우를 생각해보자. $f(K, y, z)$가 가질 수 있는 최댓값은 구간 $[l, r]$ 중 $K$ 이하의 원소의 개수이다. 이를 각 원소 관점에서 생각해본다면, 가능한 $g(K)$의 최댓값은 모든 $K$ 이하의 자연수 $i$에 대해 $i$의 값을 가지는 위치를 $p(i)$라 할 때 $p(i) \times (N-p(i)+1)$의 합임을 알 수 있다. $a_1, a_2, ..., a_N$에서 $K$ 이하의 원소만을 고른 부분수열을 $b_1, b_2, ..., b_K$라 하면, $f(K, y, z)$의 실젯값은 위에서 구한 이론적인 값에서 $b_i < b_{i+1} < b_{i+2}$ 또는..

알고리즘 sorting, segtree 시간복잡도 $O(NlogN)$ 풀이 한 가로선 또는 세로선 기준으로 두 직사각형이 구분됨이 보장됨. WLOG 자르는 선을 세로선이라 하면, 각 직사각형당 가로 길이: 미리 sort 해놓은 배열에서의 차, $O(1)$ 세로 길이: 구간에서의 $max-min$, segment tree로 $O(logN)$ (구간이 시작 또는 끝을 포함하므로 prefix/suffix max/min으로도 가능) 코드 #include using namespace std; #define ll long long int N; pair a[50005]; ll x[50005], y[50005], befans, ans = 1e18; struct z { ll mx, mn; }; z xtree[200005..

이 글은 segment tree(이하 segtree)를 완벽히 이해했음을 전제로 진행하는 글입니다. Segment tree Segment Tree segment tree가 뭔가요? segment tree(이하 segtree)는 주어진 배열에서 특정 원소 수정 구간 단위 연산의 결과(ex: 구간 합, 구간 최댓값) 를 $O(logN)$에 수행하게 해주는 알고리즘입니다. 기본 원리 작동하 seojin0305-ps.tistory.com 왜 필요한가요? segtree는 특정 원소를 수정하는 데 $O(logN)$의 시간복잡도가 소요됩니다. 그러나 특정 원소가 아닌, 특정 구간에 해당하는 모든 원소를 수정할 경우 시간복잡도는 $O(LlogN)$으로 매우 커지게 됩니다. lazy segment tree는 이를 $O(..

segment tree가 뭔가요? segment tree(이하 segtree)는 주어진 배열에서 특정 원소 수정 구간 단위 연산의 결과(ex: 구간 합, 구간 최댓값) 를 $O(logN)$에 수행하게 해주는 알고리즘입니다. 기본 원리 작동하는 기본 원리는 이분 탐색과 비슷한 듯 다릅니다. 위의 그림에서와 같이, 현재 구간에 대해 반으로 나누며 필요한 경우 새로운 구간에 대해 재귀적으로 반복하는 것입니다. 각 범위별로 구간 단위 연산의 결과를 저장해놓는다 하면, 배열의 크기가 $N$일 때 $4N$ 이하의 크기의 배열에 저장할 수 있습니다. 저장 원리는 현재 범위를 저장할 번호가 $k$라 할 때, 앞쪽 절반 배열은 $2k$, 뒤쪽 절반 배열은 $2k+1$에 저장하는 것입니다. 예시로 배열의 크기가 8이라 하..