[HEOI2016/TJOI2016] 트리
이 문제는 트리에서 노드를 표시하거나, 특정 노드로부터 가장 가까운 조상 중 표시된 노드를 찾는 쿼리를 처리해야 한다. 이를 효율적으로 해결하기 위해 경로 분할(Heavy-Light Decomposition) 기법을 사용한다. 각 경로 체인의 맨 위에 있는 표시된 노드를 관리하고, 세트(set)를 이용해 체인 내 위치를 추적한다. 쿼리는 부모 방향으로 이동하면서 각 체인의 최상단 표시 여부를 확인함으로써 O(n log n) 시간에 완료된다.
코드 예제
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, ecnt, cnt;
int fi[MAXN], ne[MAXN<<1], to[MAXN<<1];
int fa[MAXN], sz[MAXN], son[MAXN], dfn[MAXN], rnk[MAXN], top[MAXN];
set<int> chainSet[MAXN];
int firstMark[MAXN];
void addEdge(int u, int v) {
ne[++ecnt] = fi[u]; to[ecnt] = v; fi[u] = ecnt;
}
void dfs1(int u) {
sz[u] = 1;
for (int i = fi[u]; i; i = ne[i]) {
int v = to[i];
if (v == fa[u]) continue;
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int tp) {
dfn[u] = ++cnt;
rnk[cnt] = u;
top[u] = tp;
if (son[u] != -1) dfs2(son[u], tp);
for (int i = fi[u]; i; i = ne[i]) {
int v = to[i];
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
void markNode(int u) {
chainSet[top[u]].insert(dfn[u]);
firstMark[top[u]] = min(firstMark[top[u]], dfn[u]);
}
int queryAncestor(int u) {
while (u) {
if (firstMark[top[u]] <= dfn[u]) {
auto it = chainSet[top[u]].upper_bound(dfn[u]);
--it;
return rnk[*it];
}
u = fa[top[u]];
}
return -1;
}
int main() {
cin >> n >> m;
memset(son, -1, sizeof(son));
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
addEdge(u, v); addEdge(v, u);
}
dfs1(1); dfs2(1, 1);
fill(firstMark + 1, firstMark + n + 1, n + 1);
markNode(1);
while (m--) {
char op; cin >> op;
if (op == 'C') {
int u; cin >> u;
markNode(u);
} else {
int u; cin >> u;
cout << queryAncestor(u) << '\n';
}
}
}[HEOI2016/TJOI2016] 정렬
단일 쿼리를 처리하는 상황에서, 정답을 이분 탐색하는 접근이 가능하다. 원래 수열을 주어진 값보다 큰지 여부에 따라 0과 1로 변환한 후, 정렬 연산을 구간 갱신으로 시뮬레이션한다. 선분 트리를 활용하여 각 구간의 합을 빠르게 계산하고 갱신하면, 전체 복잡도는 O(n log²n)이 된다.
코드 예제
struct SegmentTree {
int n, F[4*MAXN], lazy[4*MAXN];
void pushDown(int u, int l, int r) {
if (lazy[u] == -1) return;
int mid = (l + r) / 2;
F[u<<1] = lazy[u] * (mid - l + 1);
F[u<<1|1] = lazy[u] * (r - mid);
lazy[u<<1] = lazy[u<<1|1] = lazy[u];
lazy[u] = -1;
}
void update(int u, int l, int r, int ql, int qr, int val) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
F[u] = val * (r - l + 1);
lazy[u] = val;
return;
}
pushDown(u, l, r);
int mid = (l + r) / 2;
update(u<<1, l, mid, ql, qr, val);
update(u<<1|1, mid+1, r, ql, qr, val);
F[u] = F[u<<1] + F[u<<1|1];
}
int query(int u, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && r <= qr) return F[u];
pushDown(u, l, r);
int mid = (l + r) / 2;
return query(u<<1, l, mid, ql, qr) + query(u<<1|1, mid+1, r, ql, qr);
}
};[HEOI2016/TJOI2016] 수열
최장 비감소 부분수열을 구하는 문제로, 각 위치마다 가능한 최대/최소 값 제약이 주어진다. DP 상태 전이 시 두 조건 max_prev ≤ current_val 및 prev_val ≤ min_current을 만족해야 하며, 이는 2차원 편순서 관계로 모델링할 수 있다. 분할 정복을 통해 왼쪽 반쪽에서 오른쪽 반쪽으로의 영향을 계산하고, 좌표 압축된 펜윅 트리로 최적값을 업데이트하며 O(n log²n)에 해결한다.
[HEOI2016/TJOI2016] 게임
격자판에서 폭탄을 배치하되, 같은 행이나 열에 두 개 이상 있으면 안 되며, '#'은 장애물이다. 각 행과 열에서 장애물로 나뉘어진 연속 구간을 독립적인 정점으로 보고, '*' 위치에서 해당 행 구간과 열 구간 사이에 간선을 연결한다. 이분 그래프에서 최대 매칭을 구하면 답이 되며, Dinic 알고리즘을 적용해 O(nm √(nm)) 시간에 해결 가능하다.
[HEOI2016/TJOI2016] 문자열
부분문자열 쿼리에서 두 구간의 공통 접두사 길이(LCP)를 최대화하는 문제이다. 접미사 배열(SA), 높이 배열(height), 그리고 RMQ 자료구조를 구성한 후, 정답을 이분 탐색한다. 특정 길이 mid가 가능하려면, 첫 번째 구간 내 시작 위치들 중 현재 접미사와 LCP가 mid 이상인 것이 존재해야 한다. 이를 위해 접미사 순위 기준으로 주어진 범위 내 인접한 후보를 찾기 위해 주석목 트리(Persistent Segment Tree)를 사용한다.
[HEOI2016/TJOI2016] 합
제곱 조합 수열의 합을 구하는 문제로, 스털링 수의 성질을 활용한다. 점화식을 전개하고, 합의 순서를 바꾸어 다음과 같은 형태로 정리할 수 있다:
\[ \sum_{j=0}^{n} 2^j j! \sum_{k=0}^{j} \frac{(-1)^{j-k}}{(j-k)!} \cdot \frac{k^{n+1}-1}{k!(k-1)} \]
여기서 내부 합은 컨볼루션 형태를 이루며, FFT 또는 NTT를 사용해 O(n log n)에 계산할 수 있다. 사전 계산된 팩토리얼과 역원을 이용해 다항식 곱셈을 수행하고, 결과를 결합하여 최종 답을 도출한다.