Sqrt_decomposition

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30478 문제 # 러시아워입니다! 오늘 퇴근 후, 쇼핑몰이 닫기 전에 가족 모두에게 줄 사탕을 사야 합니다. 가족들은 독점성과 균일성을 매우 중요하게 여기기 때문에, 당신은 그들을 감동시키기 위한 계획을 세웠습니다. 각 가족 구성원에게 주는 사탕은 모두 단일 브랜드여야 하며, 동일한 브랜드의 사탕을 다른 가족 구성원이 받아서는 안 됩니다. 또한, 누군가를 더 사랑한다는 사실을 들키고 싶지 않기 때문에 모든 가족 구성원이 같은 수의 사탕을 받아야 합니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2042 🧐 관찰 및 접근 # 자명한 세그먼트 트리 연습 문제이다. 기본적으로 업데이트가 없이 구간의 합을 구해야 한다면, 이는 누적합으로 빠르게 해결할 수 있다. 이때 합을 구하는 쿼리는 $O(1)$, 업데이트는 $O(N)$이다. 업데이트를 빠르게 하기 위해선, 합을 나이브하게 구하는 방법이 있겠다. 이때 합을 구하는 쿼리는 $O(N)$, 업데이트는 $O(1)$이다. 버킷을 잘 나누어서, 두 방법의 이득만을 취하면 제곱근 분할법을 이용해서 $O(Q\sqrt{N})$까지 줄일 수 있고, 해당 문제에서는 $N \leq 10^6$이므로 약 2천만정도에 바운드된다. 지금과 같이 두 노드를 합치는 것이 직관적이고 용이할 경우에는 세그먼트 트리를 쓸 수 있으며, 두 노드를 이용해 역원과 역연산을 정의할 수 있는 경우 펜윅트리도 이용할 수 있다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; SegmentTreeSum ST(N); rep(i, 0, N){ ll x; cin >> x; ST.set(i, x); } ST.build(); rep(i, 0, M+K){ ll a, b, c; cin >> a >> b >> c; if(a == 1) ST.update(b-1, c - ST.query(b-1, b-1)); else cout << ST.query(b-1, c-1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14504 🧐 관찰 및 접근 # 수열과 쿼리 1과 비슷한데, 업데이트 쿼리가 추가되었다. 같은 방법으로 풀되, 배열 정렬 말고 multiset으로 관리하면 되지 않을까? 헉, multiset에서 거리를 계산할때 쓰는 distance함수가 $O(N)$이라고 한다!! 어차피 버킷의 크기가 작으니, 나이브하게 정렬해버려도 문제가 없겠다. 💻 풀이 # 코드 (C++): const int sq = 700; struct sqrtDecomposition{ int N; vector<int> A; vector<vector<int>> bucket; sqrtDecomposition(int N, vector<int> &A): N(N), A(A){ bucket.resize((N-1)/sq+1); rep(i, 0, N) bucket[i/sq].push_back(A[i]); for(int i = 0; i < (int)bucket.size(); i++) sort(all(bucket[i])); }; void update(int i, int val){ int b = i/sq; auto it = lower_bound(all(bucket[b]), A[i]); *it = val; A[i] = val; sort(all(bucket[b])); } int query(int L, int R, int val){ int ret = 0; for(int i = L; i <= R;){ if(i%sq == 0 && i+sq-1 <= R){ ret += bucket[i/sq].end() - upper_bound(all(bucket[i/sq]), val); i += sq; } else{ ret += A[i] > val; i++; } } return ret; } }; void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; sqrtDecomposition sd(N, A); int Q; cin >> Q; while(Q--){ int op; cin >> op; if(op == 1){ int i, j, k; cin >> i >> j >> k; cout << sd.query(i-1, j-1, k) << "\n"; } else{ int i, k; cin >> i >> k; sd.update(i-1, k); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/13537 🧐 관찰 및 접근 # 부분수열에서 물어보는 쿼리가 있으니, 세그먼트 트리가 먼저 생각이 난다. 그런데 쿼리가 좀 까다롭다. 이럴때, $N, M$모두 10만이므로 제곱근 분할법을 한번 생각해보자. 수가 $C$개 들어있는 버킷을 $B$개 만든다면 $(C = N/B$), 버킷 내의 수들을 정렬하는데 $O(B \times C\log{C})$, 버킷들에 대해 답을 구하는데에 $O(B \times \log{C})$ 따라서 이들을 최소화하기 위해서는 적당히 $\sqrt{N}$보다 약간 크게 잡으면 될 것 같다. 💻 풀이 # 코드 (C++): const int sq = 700; struct sqrtDecomposition{ int N; vector<int> A; vector<vector<int>> bucket; sqrtDecomposition(int N, vector<int> &A): N(N), A(A){ bucket.resize((N-1)/sq+1); rep(i, 0, N) bucket[i/sq].push_back(A[i]); for(int i = 0; i < (int)bucket.size(); i++) sort(all(bucket[i])); }; int query(int L, int R, int val){ int ret = 0; for(int i = L; i <= R;){ if(i%sq == 0 && i+sq-1 <= R){ ret += bucket[i/sq].end() - upper_bound(all(bucket[i/sq]), val); i += sq; } else{ ret += A[i] > val; i++; } } return ret; } }; void solve(){ int N; cin >> N; vector<int> A(N); rep(i, 0, N) cin >> A[i]; sqrtDecomposition sd(N, A); int Q; cin >> Q; while(Q--){ int i, j, k; cin >> i >> j >> k; cout << sd.query(i-1, j-1, k) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/18180 번역 문제 번역 # 바이킹 락 운동에는 다양한 흐름이 존재한다. 올드 아이슬란드 그래니트 락, 미들 데니쉬 더스티 바이킹 락, 레이트 핀게일 다크 그린 락, 피오르드 볼더 아발란체 락 등, 인기 있는 흐름의 전체 목록을 나열하면 이 페이지를 여러 번 가득 채울 정도이다. 스칸디나비아 고등교육부는 이러한 흐름들이 서로 어떻게 영향을 주는지 연구하고 있다. 그들은 현재 대규모 실험을 계획 중이며, 적절히 선발된 자원봉사자들을 무인도들로 구성된 군도에 배치하여 상대적으로 긴 시간 동안 그들의 음악적 스타일과 선호도가 서로 미치는 영향을 관찰하고자 한다.