CF1814F 통신 타워: 시간 기반 분할 정복
간선의 활성화 조건이 구간으로 주어질 때, 각 정점이 1번과 연결되는 시간을 계산해야 한다. 이 문제는 선분 트리 분할 정복(Segment Tree Divide and Conquer) 기법으로 해결할 수 있다.
각 간선은 두 정점의 유효 범위 교집합에 따라 특정 시간 구간 동안만 사용 가능하다. 이를 선분 트리의 해당 구간 노드에 삽입한 후, DFS를 수행하면서 유니온 파인드로 연결성을 관리한다. 리프 노드에서는 1번 정점과 같은 집합에 속하면 답을 1 증가시킨다. 경로 압축 대신 크기 기반 합치기를 사용하고 스택으로 복원 연산을 지원하여 효율적으로 처리한다.
코드 보기
#include <bits/stdc++.h>
const int N = 4e5 + 5;
int n, m, l[N], r[N], fa[N], sz[N], tag[N], u[N], v[N], stk[N], top;
std::vector<int> op[N * 4];
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
void merge(int x, int y) {
if ((x = find(x)) == (y = find(y))) return;
if (sz[x] > sz[y]) std::swap(x, y);
tag[x] -= tag[y];
fa[x] = y;
sz[y] += sz[x];
stk[++top] = x;
}
void rollback(int bot) {
while (top != bot) {
int x = stk[top--];
tag[x] += tag[fa[x]];
sz[fa[x]] -= sz[x];
fa[x] = x;
}
}
void update(int L, int R, int s, int t, int idx, int p) {
if (R < s || t < L || L > R) return;
if (L <= s && t <= R) {
op[p].push_back(idx);
return;
}
int mid = (s + t) >> 1;
update(L, R, s, mid, idx, p << 1);
update(L, R, mid + 1, t, idx, p << 1 | 1);
}
void query(int s, int t, int p) {
int bot = top;
for (int idx : op[p]) merge(u[idx], v[idx]);
if (s == t) ++tag[find(1)];
else {
int mid = (s + t) >> 1;
query(s, mid, p << 1);
query(mid + 1, t, p << 1 | 1);
}
rollback(bot);
}
int main() {
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) {
std::cin >> l[i] >> r[i];
fa[i] = i; sz[i] = 1;
}
for (int i = 1; i <= m; ++i) {
std::cin >> u[i] >> v[i];
if (l[u[i]] > l[v[i]]) std::swap(u[i], v[i]);
update(l[v[i]], std::min(r[u[i]], r[v[i]]), 1, 200000, i, 1);
}
query(1, 200000, 1);
for (int i = 1; i <= n; ++i)
if (tag[i]) std::cout << i << ' ';
std::cout << '\n';
}P3527 MET-Meteors: 전체 이분 탐색
N개 국가가 M개 지역을 순환하며 메테오르트를 수집하는 상황에서, 각국이 목표량을 달성하는 최초 시점을 구하는 문제이다. 단순 이분 탐색은 O(N log Q)의 쿼리를 반복하여 비효율적이다.
전체 이분 탐색(Mo's Algorithm on Queries)을 적용하면, 모든 국가를 동시에 이분 탐색할 수 있다. solve(lq, rq, tl, tr) 함수는 lq~rq번 국가의 해답이 tl~tr 사이에 있음을 의미한다. 중간 지점 tm까지의 작업을 BIT로 적용한 후, 각 국가의 누적량을 확인하여 다음 재귀 범위를 결정한다. 작업 복구 후 하위 호출을 진행한다.
코드 보기
#include <bits/stdc++.h>
const int MAXN = 3e5 + 5;
int n, m, k, req[MAXN], ans[MAXN];
int a[MAXN], lef[MAXN], rig[MAXN];
long long sum[MAXN];
std::vector<int> areas[MAXN];
int temp_left[MAXN], temp_right[MAXN], q_order[MAXN];
void add(int pos, int val) {
while (pos <= m) {
sum[pos] += val;
pos += pos & -pos;
}
}
long long query(int pos) {
long long res = 0;
while (pos) {
res += sum[pos];
pos -= pos & -pos;
}
return res;
}
void solve(int ql, int qr, int tl, int tr) {
if (ql > qr) return;
if (tl == tr) {
for (int i = ql; i <= qr; ++i) ans[q_order[i]] = tl;
return;
}
int tm = (tl + tr) >> 1;
for (int i = tl; i <= tm; ++i) {
if (lef[i] <= rig[i]) {
add(lef[i], a[i]);
add(rig[i] + 1, -a[i]);
} else {
add(lef[i], a[i]);
add(1, a[i]);
add(rig[i] + 1, -a[i]);
}
}
int pl = 0, pr = 0;
for (int i = ql; i <= qr; ++i) {
long long total = 0;
for (int area : areas[q_order[i]]) total += query(area);
if (total >= req[q_order[i]])
temp_left[++pl] = q_order[i];
else {
req[q_order[i]] -= total;
temp_right[++pr] = q_order[i];
}
}
for (int i = tl; i <= tm; ++i) {
if (lef[i] <= rig[i]) {
add(lef[i], -a[i]);
add(rig[i] + 1, a[i]);
} else {
add(lef[i], -a[i]);
add(1, -a[i]);
add(rig[i] + 1, a[i]);
}
}
for (int i = 1; i <= pl; ++i) q_order[ql + i - 1] = temp_left[i];
for (int i = 1; i <= pr; ++i) q_order[ql + pl + i - 1] = temp_right[i];
solve(ql, ql + pl - 1, tl, tm);
solve(ql + pl, qr, tm + 1, tr);
}SP1805 히스토그램 최대 사각형: 카르테시안 트리
주어진 히스토그램에서 가장 큰 직사각형을 찾는 문제다. 전형적인 스택 기반 풀이 외에, 카르테시안 트리(Cartesian Tree)를 이용한 접근도 가능하다.
인덱스를 키, 높이를 우선순위로 하는 카르테시안 트리를 구성하면, 각 서브트리는 해당 구간 내 최소 높이를 루트로 갖는다. 따라서 서브트리 크기와 루트 높이의 곱이 그 구간에서 만들 수 있는 최대 사각형 면적이 된다. 오른쪽 경로를 유지하는 스택으로 트리를 구성하고, DFS로 각 노드의 서브트리 크기를 계산한 후 최댓값을 갱신한다.
코드 보기
#include <bits/stdc++.h>
const int MAXN = 2e5 + 5;
int n, h[MAXN], left_ch[MAXN], right_ch[MAXN];
int stk[MAXN], top;
long long result;
void dfs(int u) {
int size = 1;
if (left_ch[u]) { dfs(left_ch[u]); size += left_ch[u]; }
if (right_ch[u]) { dfs(right_ch[u]); size += right_ch[u]; }
result = std::max(result, 1LL * size * h[u]);
}
int main() {
while (std::cin >> n && n) {
for (int i = 1; i <= n; ++i) {
std::cin >> h[i];
int pos = top;
while (pos && h[stk[pos]] > h[i]) --pos;
if (pos) right_ch[stk[pos]] = i;
if (pos < top) left_ch[i] = stk[pos + 1];
stk[++pos] = i;
top = pos;
}
int root = 1;
for (int i = 1; i <= n; ++i) {
if (!left_ch[i] && !right_ch[i]) root = i;
}
result = 0;
dfs(root);
std::cout << result << '\n';
// reset
std::fill(left_ch + 1, left_ch + n + 1, 0);
std::fill(right_ch + 1, right_ch + n + 1, 0);
top = 0;
}
}P3792 유우노와 아이돌 숭배: 세그먼트 트리와 집합
수열의 부분 구간이 연속한 자연수의 순열인지 판별하는 문제다. 조건은 두 가지: 값의 중복 없음, 최대-최소+1이 길이와 같음.
세그먼트 트리로 구간의 최댓값, 최솟값, 그리고 각 원소의 이전 등장 위치(pre)의 최댓값을 관리한다. pre 배열은 같은 값을 가진 이전 인덱스를 저장하며, set 자료구조로 각 값의 위치들을 관리한다. 업데이트 시 set을 수정하고, 관련된 pre 값을 갱신한다. 쿼리 시 pre의 최댓값이 구간 시작보다 작고, 최대-최소+1이 길이와 같으면 성립한다.
코드 보기
#include <bits/stdc++.h>
const int MAXN = 5e5 + 5;
struct Node {
int max_val, min_val, prev_max;
Node operator+(const Node& rhs) const {
return { std::max(max_val, rhs.max_val),
std::min(min_val, rhs.min_val),
std::max(prev_max, rhs.prev_max) };
}
} tree[MAXN * 4];
int arr[MAXN], last_pos[MAXN * 2], prev_idx[MAXN];
std::set<int> positions[MAXN * 2];
std::vector<int> unique_vals;
int compress(int x) {
return std::lower_bound(unique_vals.begin(), unique_vals.end(), x) - unique_vals.begin();
}
void push_up(int p) { tree[p] = tree[p<<1] + tree[p<<1|1]; }
void build(int s, int t, int p) {
if (s == t) {
tree[p] = { arr[s], arr[s], prev_idx[s] };
return;
}
int mid = (s + t) >> 1;
build(s, mid, p<<1); build(mid+1, t, p<<1|1);
push_up(p);
}
Node query(int L, int R, int s, int t, int p) {
if (L <= s && t <= R) return tree[p];
int mid = (s + t) >> 1;
if (R <= mid) return query(L, R, s, mid, p<<1);
if (L > mid) return query(L, R, mid+1, t, p<<1|1);
return query(L, R, s, mid, p<<1) + query(L, R, mid+1, t, p<<1|1);
}
void modify(int pos, int new_val) {
// update set and prev values
}CF1515I Phoenix와 다이아몬드: 값역 기반 분할
무게, 가치, 개수가 주어진 보석들을 배낭에 넣는 문제로, 무게 제한 내에서 최대 가치를 얻는다. 추가로 개수 변경 쿼리도 존재한다.
로그 스케일의 값역 그룹화(Value Bucketing)를 사용한다. 각 그룹 i는 무게가 [2^i, 2^(i+1))인 항목들을 포함한다. 세그먼트 트리 노드는 각 그룹별로 W_i(sum of weight), V_i(sum of value), T_i(해당 그룹 첫 항목 획득 위한 최소 용량)을 저장한다.
쿼리 시 현재 용량 c의 그룹을 찾고, W_{i+1} ≤ c면 모두 취득, W_i ≤ c < T_i면 낮은 그룹만 취득, 아니면 좌우 자식으로 내려간다. 한 번의 내림마다 c의 effective depth가 줄어들므로 O(log n log V) 시간에 완료된다.
코드 보기
#include <bits/stdc++.h>
const int MAXN = 2e5 + 5;
const int LOG_V = 17;
long long value_sum[MAXN*4][LOG_V+1], weight_sum[MAXN*4][LOG_V+1];
long long needed[MAXN*4][LOG_V+1], cnt[MAXN];
int weight[MAXN], worth[MAXN], index_map[MAXN], rev_index[MAXN];
int get_log(long long w) {
if (w == 0) return 0;
int res = 0;
while ((1LL << (res + 1)) <= w) ++res;
return std::min(res, LOG_V - 1);
}
void combine(int p) {
for (int i = 0; i <= LOG_V; ++i) {
value_sum[p][i] = value_sum[p<<1][i] + value_sum[p<<1|1][i];
weight_sum[p][i] = weight_sum[p<<1][i] + weight_sum[p<<1|1][i];
needed[p][i] = std::min(needed[p<<1][i], weight_sum[p<<1][i] + needed[p<<1|1][i]);
}
}P4755 아름다운 쌍: 히스토그램 분할 정복
a_i × a_j ≤ max(a_i, ..., a_j)를 만족하는 (i,j) 쌍의 수를 세는 문제다. 최댓값을 기준으로 구간을 나누고, 작은 쪽을 고정하여 큰 쪽에서 조건을 만족하는 원소 수를 세그먼트 트리로 센다.
각 분할 단계에서 더 짧은 쪽을 선택하여 반대편에서 쿼리를 날린다. 세그먼트 트리는 값의 출현 빈도를 관리하며, a_p / a_i 이하의 값들의 개수를 반환한다. 전체 복잡도는 O(n log² n).
코드 보기
#include <bits/stdc++.h>
const int MAXN = 2e5 + 5;
const int MAXV = 1e9;
int arr[MAXN], root[MAXN], node_cnt;
int left_son[MAXN * 30], right_son[MAXN * 30], count_node[MAXN * 30];
long long answer;
void insert(int value, int s, int t, int old_root, int& new_root) {
new_root = ++node_cnt;
count_node[new_root] = count_node[old_root] + 1;
left_son[new_root] = left_son[old_root];
right_son[new_root] = right_son[old_root];
if (s == t) return;
int mid = (s + t) >> 1;
if (value <= mid)
insert(value, s, mid, left_son[old_root], left_son[new_root]);
else
insert(value, mid+1, t, right_son[old_root], right_son[new_root]);
}
int query_count(int limit, int s, int t, int left_root, int right_root) {
if (t <= limit) return count_node[right_root] - count_node[left_root];
if (s > limit) return 0;
int mid = (s + t) >> 1;
return query_count(limit, s, mid, left_son[left_root], left_son[right_root]) +
query_count(limit, mid+1, t, right_son[left_root], right_son[right_root]);
}Atcoder AGC001E BBQ Hard: 조합적 변환
Σ C(a_i+b_i+a_j+b_j, a_i+a_j)를 계산하는 문제다. 직접 계산은 O(N²)으로 불가능하다.
조합의 의미를 해석하면 (-a_i, -b_i)에서 (a_j, b_j)까지 오른쪽/위쪽 이동만으로 가는 경로 수와 같다. 모든 음수 좌표에 초기값 1을 설정한 후, DP로 전체 격자에 대해 경로 수를 계산한다. 이후 각 (a_j, b_j) 위치의 값을 더한 후, 자기 자신에 대한 중복 계산을 빼고 2로 나눈다.
코드 보기
#include <bits/stdc++.h>
const int SIZE = 8005;
const int OFFSET = 2000;
const int MOD = 1e9 + 7;
int n, a[200005], b[200005];
long long dp[SIZE][SIZE], fact[8005], inv_fact[8005];
long long power(long long base, int exp) {
long long result = 1;
while (exp) {
if (exp & 1) result = result * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return result;
}
long long comb(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}
int main() {
std::cin >> n;
fact[0] = 1;
for (int i = 1; i <= 8000; ++i) fact[i] = fact[i-1] * i % MOD;
inv_fact[8000] = power(fact[8000], MOD - 2);
for (int i = 8000; i >= 1; --i) inv_fact[i-1] = inv_fact[i] * i % MOD;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i] >> b[i];
++dp[OFFSET - a[i]][OFFSET - b[i]];
}
for (int i = 0; i <= 4000; ++i)
for (int j = 0; j <= 4000; ++j) {
if (i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
if (j) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
}
long long ans = 0;
for (int i = 1; i <= n; ++i)
ans = (ans + dp[OFFSET + a[i]][OFFSET + b[i]] - comb(2*a[i]+2*b[i], 2*a[i]) + MOD) % MOD;
ans = ans * power(2, MOD - 2) % MOD;
std::cout << ans << '\n';
}