CDQ 분할 정복 개요
CDQ 분할 정복은 복수의 쌍 (i, j)에 대해 왼쪽 구간과 오른쪽 구간 간의 상관 관계를 효율적으로 계산하는 기법입니다. 이는 주로 순서가 중요한 쿼리 문제에서 사용되며, 분할과 정복 과정 중에 왼쪽 데이터가 오른쪽 데이터에 미치는 영향을 집계합니다.
문제 예시: 3차원 편향 쿼리 (P3810)
각 요소는 세 가지 차원 a, b, c로 구성되며, 조건 a_i ≤ a_j, b_i ≤ b_j, c_i ≤ c_j를 만족하는 쌍의 수를 세야 합니다. 이를 위해 먼저 a 기준으로 정렬하고, 이후 분할 정복을 수행하면서 b 값이 정렬된 상태로 유지됩니다.
- 분할 단계에서는 왼쪽 구간의 모든 요소가 오른쪽 구간의 요소보다 작은
a값을 가집니다. - 합치기 과정에서
b값을 기준으로 비교하며,c값은 트리 자료구조(예: 이진 인덱스 트리)로 관리하여 범위 합을 빠르게 계산합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
int n, k, cnt, tree[200005], result[MAXN], bucket[MAXN];
struct Point {
int a, b, c, id, count;
} arr[MAXN], temp[MAXN];
inline int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); }
return s * f;
}
bool cmp(const Point& x, const Point& y) {
if (x.a != y.a) return x.a < y.a;
if (x.b != y.b) return x.b < y.b;
return x.c < y.c;
}
void update(int idx, int val) {
for (; idx <= k; idx += idx & (-idx)) tree[idx] += val;
}
int query(int idx) {
int res = 0;
for (; idx; idx -= idx & (-idx)) res += tree[idx];
return res;
}
void divide_conquer(int left, int right) {
if (left == right) return;
int mid = (left + right) >> 1;
divide_conquer(left, mid);
divide_conquer(mid + 1, right);
int i = left, j = mid + 1, pos = left;
while (pos <= right) {
if (j > right || (i <= mid && arr[i].b <= arr[j].b)) {
update(arr[i].c, arr[i].count);
temp[pos++] = arr[i++];
} else {
result[arr[j].id] += query(arr[j].c);
temp[pos++] = arr[j++];
}
}
// 복원: 왼쪽 구간의 영향 제거
for (int idx = left; idx <= mid; ++idx)
update(arr[idx].c, -arr[idx].count);
// 원본 배열 복사
for (int idx = left; idx <= right; ++idx)
arr[idx] = temp[idx];
}
int main() {
n = read(), k = read();
for (int i = 1; i <= n; ++i) {
arr[i] = {read(), read(), read()};
}
sort(arr + 1, arr + n + 1, cmp);
// 중복 제거 및 카운트 저장
for (int i = 1; i <= n; ++i) {
if (i == 1 || arr[i].a != arr[i-1].a || arr[i].b != arr[i-1].b || arr[i].c != arr[i-1].c)
arr[++cnt] = arr[i];
arr[cnt].count = 1;
arr[cnt].id = cnt;
}
divide_conquer(1, cnt);
// 결과 누적
for (int i = 1; i <= cnt; ++i)
result[i] += arr[i].count - 1, bucket[result[i]] += arr[i].count;
for (int i = 0; i < n; ++i)
cout << bucket[i] << '\n';
return 0;
}
점 추가 및 사각형 쿼리 (P4390 – Mokia)
이 문제는 시간에 따라 점이 추가되고, 특정 사각형 내부의 합을 요청하는 쿼리가 있습니다. 이를 해결하기 위해 좌표압축 + CDQ 분할 정복 + 이진 인덱스 트리를 결합합니다.
- 쿼리 시점에 따라 정렬하고,
opt=1은 점 삽입,opt=2는 쿼리입니다. - 쿼리는 4개의 사각형으로 나누어 처리 (상하좌우 포함/제외)하여 범위 합을 계산합니다.
- 분할 정복 중 왼쪽 구간의 삽입이 오른쪽 구간의 쿼리에 영향을 미칩니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int w, cnt, q_count, op, ans[10005], tree[2000005];
struct Query {
int x, y, op, val, factor, id;
} queries[MAXN], temp[MAXN];
inline int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); }
return s * f;
}
bool cmp(const Query& a, const Query& b) {
if (a.id != b.id) return a.id < b.id;
return a.op > b.op; // 쿼리가 삽입보다 앞서도록
}
void add(int idx, int val) {
for (; idx <= w; idx += idx & (-idx)) tree[idx] += val;
}
int get_sum(int idx) {
int res = 0;
for (; idx; idx -= idx & (-idx)) res += tree[idx];
return res;
}
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
int i = l, j = mid + 1, pos = l;
while (pos <= r) {
if (j > r || (i <= mid && queries[i].x <= queries[j].x)) {
if (queries[i].op == 1) add(queries[i].y, queries[i].val);
temp[pos++] = queries[i++];
} else {
if (queries[j].op == 2)
ans[queries[j].id] += queries[j].factor * get_sum(queries[j].y);
temp[pos++] = queries[j++];
}
}
// 왼쪽 삽입 삭제
for (int idx = l; idx <= mid; ++idx)
if (queries[idx].op == 1) add(queries[idx].y, -queries[idx].val);
for (int idx = l; idx <= r; ++idx)
queries[idx] = temp[idx];
}
int main() {
op = read(), w = read() + 1;
while ((op = read()) != 3) {
if (op == 1) {
int x = read() + 1, y = read() + 1, v = read();
queries[++cnt] = {x, y, 1, v, 0, q_count};
} else if (op == 2) {
int xa = read() + 1, ya = read() + 1, xb = read() + 1, yb = read() + 1;
queries[++cnt] = {xa - 1, ya - 1, 2, 0, 1, ++q_count};
queries[++cnt] = {xb, ya - 1, 2, 0, -1, q_count};
queries[++cnt] = {xa - 1, yb, 2, 0, -1, q_count};
queries[++cnt] = {xb, yb, 2, 0, 1, q_count};
}
}
sort(queries + 1, queries + cnt + 1, cmp);
cdq(1, cnt);
for (int i = 1; i <= q_count; ++i)
cout << ans[i] << '\n';
return 0;
}
동적 역순쌍 계산 (P3157 – CQOI2011)
배열에서 특정 위치의 원소를 제거할 때 발생하는 역순쌍의 변화량을 계산해야 합니다. 이를 위해 원소 제거를 "시간"에 따른 추가로 변환하고, 각 원소가 언제 추가되었는지 기록합니다.
- CDQ 분할 정복에서 시간 순서로 정렬된 원소를 처리합니다.
- 왼쪽에서 오른쪽으로 진행하면서, 현재 위치보다 앞선 위치에 있는 큰 값과, 뒤에 있는 작은 값을 모두 고려해 역순쌍을 계산합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int n, m, pos[MAXN], tree[MAXN];
ll ans[MAXN];
struct Event {
int idx, value, time;
} events[MAXN], temp[MAXN];
inline int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar(); }
return s * f;
}
bool cmp(const Event& a, const Event& b) {
return a.time < b.time;
}
void add(int idx, int val) {
for (; idx <= n; idx += idx & (-idx)) tree[idx] += val;
}
int get_sum(int idx) {
int res = 0;
for (; idx; idx -= idx & (-idx)) res += tree[idx];
return res;
}
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
int i = l, j = mid + 1, pos = l;
while (pos <= r) {
if (j > r || (i <= mid && events[i].idx < events[j].idx)) {
add(events[i].value, 1);
temp[pos++] = events[i++];
} else {
ans[events[j].time] += get_sum(n) - get_sum(events[j].value);
temp[pos++] = events[j++];
}
}
for (int idx = l; idx <= mid; ++idx)
add(events[idx].value, -1);
i = mid, j = r;
while (i >= l || j >= mid + 1) {
if (j < mid + 1 || (i >= l && events[i].idx > events[j].idx))
add(events[i--].value, 1);
else
ans[events[j--].time] += get_sum(events[j].value);
}
for (int idx = l; idx <= mid; ++idx)
add(events[idx].value, -1);
for (int idx = l; idx <= r; ++idx)
events[idx] = temp[idx];
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) {
events[i] = {i, read()};
pos[events[i].value] = i;
}
for (int i = 1; i <= m; ++i)
events[pos[read()]].time = m - i + 1;
sort(events + 1, events + n + 1, cmp);
solve(1, n);
for (int i = 1; i <= m; ++i)
ans[i] += ans[i - 1];
for (int i = m; i >= 1; --i)
cout << ans[i] << '\n';
return 0;
}