이 문서에서는 다양한 자료구조 문제들을 다루며, 세그먼트 트리, 블록 분할, 그리고 코뜰리 트리(ODT)를 활용한 풀이를 소개한다.

P6812 「MCOI-02」조상 (Ancestor)

문제에서 정의한 "조상"은 비내림차순 수열이다. 이를 판별하기 위해 차분 배열을 활용하여 세그먼트 트리로 구간 최솟값을 관리할 수 있다. 차분 배열의 구간 최솟값이 0 이상이면 해당 구간은 비내림차순이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1145140;

int n, k, a[N];
ll diff[N]; // 차분 배열

struct SegTree {
    int l, r;
    ll mn;
} tree[4 * N];

void build(int node, int l, int r) {
    tree[node].l = l; tree[node].r = r;
    if (l == r) {
        tree[node].mn = a[l + 1] - a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
}

void update(int node, int pos, ll delta) {
    if (tree[node].l == tree[node].r) {
        tree[node].mn += delta;
        return;
    }
    int mid = (tree[node].l + tree[node].r) >> 1;
    if (pos <= mid) update(node * 2, pos, delta);
    else update(node * 2 + 1, pos, delta);
    tree[node].mn = min(tree[node * 2].mn, tree[node * 2 + 1].mn);
}

ll query(int node, int ql, int qr) {
    if (ql <= tree[node].l && tree[node].r <= qr) return tree[node].mn;
    int mid = (tree[node].l + tree[node].r) >> 1;
    ll res = 1e18;
    if (ql <= mid) res = min(res, query(node * 2, ql, qr));
    if (qr > mid) res = min(res, query(node * 2 + 1, ql, qr));
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n - 1);
    for (int i = 1; i <= k; ++i) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (r == n + 1) r = n;
        if (op == 1) {
            cin >> x;
            if (l > 1) update(1, l - 1, x);
            update(1, r, -x);
        } else {
            cout << (query(1, l, r - 1) >= 0 ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

P4344 [SHOI2015] 뇌동 치료기

이 문제는 세그먼트 트리를 이용해 구간을 0 또는 1로 덮어쓰는 연산과 최장 연속 0의 길이를 구하는 연산을 처리한다. 각 노드는 왼쪽, 오른쪽, 전체에서의 최대 연속 0의 길이(lmax, rmax, max)와 1의 개수(sum)를 저장한다. 덮어쓰기 연산 시 구간 내 1의 개수를 파악하여 0의 구간을 채우는 방식으로 구현한다.

// 주요 코드 구조 (세그먼트 트리 pushup 함수)
void pushup(int node) {
    tree[node].sum = tree[left].sum + tree[right].sum;
    // lmax, rmax, max 계산 생략
}

E. Colorful Operations

코뜰리 트리(ODT)를 기본으로 사용한다. 색상별로 덧셈 태그를 관리하며, 구간 덮어쓰기 시 원래 색상의 태그를 반영한 후 새로운 색상의 태그를 차감한다. 구간 덧셈은 펜윅 트리를 이용해 빠르게 수행하며, 단일 원소 조회 시 펜윅 트리 값 + 색상 태그를 출력한다.

// ODT assign 함수 핵심 로직
void assign(int l, int r, int col) {
    auto itr = split(r + 1), itl = split(l);
    for (auto it = itl; it != itr; ++it) {
        add(it->l, colorTag[it->v]);
        add(it->r + 1, -colorTag[it->v]);
    }
    s.erase(itl, itr);
    s.insert(Node(l, r, col));
    add(l, -colorTag[col]);
    add(r + 1, colorTag[col]);
}

P8818 [CSP-S 2022] 전략 게임

두 수열 A, B에서 각각 구간을 선택하여 곱의 최댓값을 구하는 문제이다. 세그먼트 트리로 A의 최댓값, 최솟값, 0의 존재 여부, 가장 작은 양수, 가장 큰 음수를 관리하고, B의 최댓값, 최솟값, 0의 존재 여부를 관리한다. 이후 B 구간의 부호 특성과 A 구간의 수의 분포에 따라 경우를 나누어 최적의 곱을 계산한다.

// 분류 조건 예시
if (minB >= 0) { // B의 모든 원소가 0 이상
    if (maxA <= 0) ans = maxA * maxB;
    else if (minA >= 0) ans = maxA * minB;
    else ans = maxA * minB;
}

P4135 시 짓기

블록 단위로 각 숫자의 등장 횟수 누적합을 전처리한다. 전체 구간의 정답은 블록 간의 정답과 양쪽 산발 블록의 숫자 등장 횟수를 합하여 계산한다. 산발 블록의 각 숫자에 대해 전체 구간에서의 등장 횟수가 짝수인지 여부를 갱신한다.

// 블록 간 정답 계산 루틴
long long ans = blockAns[leftBlock + 1][rightBlock - 1];
// 산발 블록 처리 후 ans 갱신

P2572 [SCOI2010] 수열 연산

0과 1로 이루어진 수열에 대해 구간 덮어쓰기, 구간 반전, 구간 내 1의 개수 조회, 최장 연속 1의 길이 조회를 처리한다. 세그먼트 트리에 0과 1 각각의 연속 길이 정보를 저장하고, 덮어쓰기와 반전 태그의 우선순위를 적절히 관리해야 한다. 반전 연산 시 0과 1의 정보를 swap한다.

// 반전 연산 처리
void reverseNode(int node) {
    swap(tree[node].max1, tree[node].max0);
    swap(tree[node].lmax1, tree[node].lmax0);
    swap(tree[node].rmax1, tree[node].rmax0);
    tree[node].sum = tree[node].len - tree[node].sum;
}

P3863 수열

특정 시점까지의 구간 덧셈 업데이트를 반영한 후, 특정 위치의 값이 특정 값 이상인 시점의 개수를 구하는 문제이다. 시간 축을 분할하고 스위핑 기법을 사용한다. 각 업데이트를 시작점과 끝점으로 분해하여 시간 순으로 처리하며, 블록 내에서 이분 탐색을 통해 조건을 만족하는 개수를 센다.

// 시간 블록 내 이분 탐색
int pos = -1;
int lo = st[i], hi = ed[i];
while (lo <= hi) {
    int mid = (lo + hi) >> 1;
    if (sortedVal[mid] + blockTag[i] >= target) {
        pos = mid;
        lo = mid + 1;
    } else hi = mid - 1;
}
ans += (pos != -1 ? pos - st[i] + 1 : 0);

P2787 언어 1 (chin1) - 이성적 사고

알파벳 26개로 이루어진 문자열에 대해 구간 내 특정 문자의 개수 조회, 구간 덮어쓰기, 구간 정렬을 처리한다. 코뜰리 트리로 구현할 수 있으며, 정렬 연산은 구간 내 각 문자의 개수를 센 후 순서대로 다시 삽입하는 방식으로 동작한다.

// 구간 정렬 연산
void sortRange(int l, int r) {
    int cnt[26] = {0};
    // ... ODT 구간 분할 및 개수 카운트
    s.erase(itl, itr);
    int pos = l;
    for (int i = 0; i < 26; ++i) {
        if (cnt[i]) {
            s.insert({pos, pos + cnt[i] - 1, i});
            pos += cnt[i];
        }
    }
}

E. A Simple Task

P2787과 유사하게, 알파벳 26개로 이루어진 문자열을 코뜰리 트리로 관리하며 구간 정렬(오름차순 또는 내림차순)을 수행한다. 값의 범위가 작아 코뜰리 트리가 효율적으로 동작한다.

// 내림차순 정렬
void sortDesc(int l, int r) {
    // ... 개수 카운트 후
    for (int i = 25; i >= 0; --i) {
        if (cnt[i]) {
            s.insert({pos, pos + cnt[i] - 1, i});
            pos += cnt[i];
        }
    }
}

SPOJ GSS 시리즈

최대 부분합을 구하는 일련의 문제들이다. GSS1은 기본형으로, 세그먼트 트리를 이용해 구간의 최대 부분합을 pushup에서 합성한다. GSS3은 단일 원소 수정을 추가한다. GSS5는 두 구간이 주어졌을 때 부분합의 최댓값을 구하며, 구간이 겹치는 경우와 겹치지 않는 경우를 나누어 처리한다.

// GSS1 pushup
void pushup(Node &par, Node &l, Node &r) {
    par.sum = l.sum + r.sum;
    par.lmax = max(l.lmax, l.sum + r.lmax);
    par.rmax = max(r.rmax, r.sum + l.rmax);
    par.best = max({l.best, r.best, l.rmax + r.lmax});
}

P1972

정적 배열에서 구간 내 서로 다른 수의 개수를 구하는 문제이다. 오프라인으로 쿼리를 정렬한 후, 펜윅 트리를 이용해 각 숫자의 마지막 등장 위치에만 1을 표시하여 구간 합으로 답을 구한다.

for (int i = 1; i <= n; ++i) {
    fenwick.add(i, 1);
    fenwick.add(last[a[i]], -1);
    last[a[i]] = i;
    // 현재 오른쪽 끝이 i인 쿼리 처리
}

P4113

P1972의 응용으로, 구간 내에서 두 번 이상 등장하는 숫자의 개수를 센다. 각 숫자의 두 번째 등장 위치에 1을 표시하고, 이전 등장 위치는 -1로 갱신하여 펜윅 트리로 관리한다.

fenwick.add(lastPos, 1);
fenwick.add(lastLastPos, -1);

P8360 [SNOI2022] 군대

블록 단위로 유니온-파인드를 사용하여 각 색상의 개수와 덧셈 태그를 관리한다. 색상 변경 시, 블록의 루트 노드를 합치거나 색상을 변경한다. 구간 덧셈은 블록의 루트 노드에 태그를 추가하고, 블록의 합계를 갱신한다. 단일 원소 조회는 파인드 연산을 통해 태그를 모두 더한 후 기본값에 더하여 계산한다.

// 블록 내 특정 색상 병합
int p1 = root[blockId][x], p2 = root[blockId][y];
if (!p1) continue;
if (p2) {
    unionSet(p1, p2);
} else {
    changeColor(p1, y);
}