오프라인 쿼리

온라인 vs 오프라인

온라인은 질의를 받는 즉시 답해야 하고, 이전 답이 다음 입력에 영향을 줄 수
있다. 오프라인은 모든 질의를 미리 받아 둘 수 있어, 유리한 순서로 재배열해
처리할 수 있다. 이 자유도가 오프라인 기법의 힘이다.

핵심 발상: "질의에 답하는 순서는 입력 순서와 같을 필요가 없다." 질의를 정렬
하거나 묶어 처리하면 자료 구조의 갱신 횟수를 극적으로 줄일 수 있다.

대표 패턴 1: 정렬 후 스위핑

질의와 원소를 같은 기준(보통 값이나 좌표)으로 정렬하고, 포인터를 전진시키며
"지금까지 조건을 만족하는 원소"만 자료 구조에 반영한 상태에서 답한다.

예: "각 질의 \((x_q)\)에 대해 값이 \(x_q\) 이하인 원소들 중 ...". 질의를 \(x_q\)
오름차순으로 정렬하고, 원소도 값 오름차순으로 보면서 포인터를 밀면, 각 원소는
정확히 한 번만 자료 구조에 삽입된다. 삽입 총 \(O(N \log N)\), 질의 총
\(O(Q \log N)\).

대표 패턴 2: 좌표·시간 차원 추가

2차원 직사각형 질의를 한 축으로 정렬해 1차원 문제 \(\times\) 스위프로 낮춘다.
"점 추가 / 직사각형 안 점 개수" 같은 문제가 전형적인데, 질의를 누적 합 형태로
쪼개(포함-배제) y축 BIT/세그 트리에 올린다.

대표 패턴 3: 차분으로 질의 분해

구간 질의 \([l, r]\)을 \(f(r) - f(l-1)\)로 쪼개면, 각 끝점을 독립된 "한쪽
질의"로 만들 수 있다. 이렇게 쪼갠 끝점들을 모아 정렬해 한 번의 스위프로 모두
처리한다.

왜 빠른가

온라인이라면 각 질의마다 자료 구조를 처음부터 세우거나 비싼 연산을 해야 할 수
있다. 오프라인은 상태를 단조롭게 키워 가며(원소를 한 번씩만 추가) 모든 질의를
한 번의 스위프로 답하므로, 갱신 비용이 질의 사이에 분할상환된다.

한계

• 답이 다음 질의에 영향을 주는 진짜 온라인 강제(예: XOR로 인덱스 인코딩)는
  오프라인이 불가능하다. 이럴 땐 퍼시스턴트 자료 구조가 필요하다.
• 질의를 모두 저장할 메모리가 있어야 한다.

오프라인은 그 자체로 알고리즘이라기보다 사고 틀이다. Mo's 알고리즘,
오프라인 동적 연결성, 병렬 이분 탐색이 모두 이 틀의 발전형이다.

예제: 구간 내 서로 다른 수의 개수

배열이 주어지고 여러 질의 \([l, r]\)에 대해 "구간 안 서로 다른 값의 개수"를
오프라인으로 구해 보자. 질의를 \(r\) 오름차순으로 정렬하고, \(r\)을 늘리며
"각 값이 마지막으로 등장한 위치"에만 1을 표시하는 BIT를 유지한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
int n, q, a[MAXN], bit[MAXN], ans[MAXN], last_pos[1000001];

void update(int i, int v) { for (; i <= n; i += i & -i) bit[i] += v; }
int sum(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    vector<array<int,3>> Q(q);   // (r, l, 질의번호)
    for (int i = 0; i < q; i++) {
        int l, r; scanf("%d %d", &l, &r);
        Q[i] = {r, l, i};
    }
    sort(Q.begin(), Q.end());    // r 오름차순

    int cur = 1;                 // 다음에 추가할 인덱스
    for (auto& [r, l, idx] : Q) {
        while (cur <= r) {       // r까지 원소를 한 번씩만 반영
            int v = a[cur];
            if (last_pos[v]) update(last_pos[v], -1); // 이전 위치 표시 제거
            update(cur, 1);                           // 현재 위치에 표시
            last_pos[v] = cur;
            cur++;
        }
        ans[idx] = sum(r) - sum(l - 1);  // [l, r]의 표시 개수 = 서로 다른 수
    }
    for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
    return 0;
}

핵심은 각 값에 대해 가장 오른쪽 등장 위치에만 1을 둔다는 것이다. \(r\)이
커질 때 같은 값이 다시 나오면 옛 위치의 1을 지우고 새 위치에 1을 둔다. 그러면
"\([l, r]\)에서 1의 합 = 서로 다른 값의 개수"가 된다.

흔한 실수

• 답 저장 순서 — 질의를 정렬했으므로 원래 입력 순서대로 출력하려면 질의
  번호를 함께 들고 다녀야 한다.
• 포인터 비단조 이동 — 이 패턴은 \(r\)이 단조 증가할 때만 포인터 한 방향
  이동이 성립한다. \(l\)도 움직여야 하면 Mo's 알고리즘이 필요하다.
• 갱신·복구 비대칭 — 삽입과 제거를 정확히 대칭으로 해야 상태가 망가지지
  않는다.

언제 무엇을 쓰나

오프라인 사고는 "이 질의들, 순서를 바꾸면 더 싸게 답할 수 있나?"를 늘 자문하는
습관에서 나온다. 정렬·차분·스위프 세 도구의 조합을 자유롭게 다루는 것이 목표다.