-
[BOJ] 10167: 금광
10167: 금광 풀이 이 문제와 비슷하게 분할정복으로 접근한다. x축을 기준으로 정렬해서, 모든 [l, r] 구간에서 최댓값을 하나씩 찾을 것이다. 시작점을 하나 정해놓고, 끝점까지 스위핑 하면서 최댓값을 찾아 주자. 스위핑이 하나 전진할 때마다 분할정복 트리를 업데이트 해 주면 된다. 이러한 구간이 많아야 3000^2개이므로 여기에 로그 붙여도 충분하다. 세그트리 업데이트 하는 느낌으로 분할정복을 하면 된다. 나는 멍청하게 구간합 업데이트를 펜윅트리 써서 했는데 여러분들은 그러지 말자. ㅋㅋㅋㅋ 까다로운 반례가 있으므로 주의하자. 코드 #include <cstdio> #include <algorithm> #include <vector>...
-
[BOJ] 16993 : 연속합과 쿼리
16993: 연속합과 쿼리 풀이 분할정복 하는 느낌, 혹은 세그트리 짜는 느낌으로 접근하면 된다. 노드 하나에 3개의 값이 들어가는데, mmax(s, e) = 가운데를 지나는 구간의 최대 합 lmax(s, e) = s를 포함하는 구간의 최대 합 rmax(s, e) = e를 포함하는 구간의 최대 합 위의 것들을 분할정복 하듯이 전처리해서 들고 있는다. 그리고 재귀 세그트리 짜듯이 쿼리를 날리면 쿼리 당 O(log N)에 답을 계산할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll...
-
[BOJ] 15561 : 구간 합 최대? 2
15561 : 구간 합 최대? 2 풀이 max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i)) = max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V 모든 A[i]를 U * A[i] + V로 바꿔주면 max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다. 15560번에 비해 범위가 크므로 세그먼트 트리 등등을 이용해주자. 코드 #include <cstdio> #include <algorithm>...
-
[BOJ] 2042 : 구간 합 구하기
2042 : 구간 합 구하기 풀이 세그트리를 짜보자~ 코드 #include <iostream> using namespace std; typedef long long ll; const int n_ = 1048576 + 1; int n, m, k, arr[n_]; ll tree[n_ * 2]; ll init(int now, int lft, int rgt) { if (lft == rgt) return tree[now] = arr[lft]; return tree[now] = init(now * 2, lft, (lft + rgt) / 2) + init(now * 2 + 1, (lft + rgt) / 2 + 1,...
-
[BOJ] 14438 : 수열과 쿼리 17
14438 : 수열과 쿼리 17 풀이 sqrt decomposition을 이용해서 풀었다. 물론 segment tree를 이용하면 훨씬 더 빠르다. 코드 #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; int n, m, sqr, a[100001], bkt[100001]; void upd(int i, int v) { a[i] = v, bkt[i / sqr] = 1e9 + 1e8; int tmp = i / sqr; for (int j = tmp * sqr; j < (tmp + 1) * sqr; j++) bkt[tmp] = min(bkt[tmp], a[j]); }...