구간 내 서로 다른 숫자의 개수를 효율적으로 계산하는 문제를 고려해 보겠습니다. 단순한 접근은 매번 좌우 끝점을 이동하며 답을 갱신하는 것이지만, 이 방식은 O(n²) 시간이 소요됩니다. 모스 알고리즘은 이 문제를 효율적으로 해결하기 위해 고안되었습니다.

모스 알고리즘은 쿼리를 오프라인으로 처리하고 블록 기반 정렬을 적용합니다. 배열을 √n 크기의 블록으로 분할한 후, 왼쪽 끝점이 속한 블록을 기준으로 먼저 정렬합니다. 동일 블록 내에서는 오른쪽 끝점을 기준으로 정렬합니다. 이때 오른쪽 끝점은 각 블록 내에서 단조 증가하므로 총 이동 횟수는 O(n√n)입니다. 왼쪽 끝점은 블록 내에서 최대 √n번 이동하며, 전체 이동 횟수 역시 O(n√n)입니다. 따라서 전체 시간 복잡도는 O(n√n)이 됩니다.

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAX_N = 200000;
const int MAX_VAL = 1000000;

struct Query {
    int start, end, idx;
};

int arr[MAX_N], block[MAX_N], freq[MAX_VAL], result[MAX_N];
int n, total_queries, distinct_cnt;

bool cmp(Query a, Query b) {
    if (block[a.start] != block[b.start]) 
        return a.start < b.start;
    return (a.start & 1) ? a.end < b.end : a.end > b.end;
}

int main() {
    cin >> n;
    int block_size = sqrt(n);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        block[i] = (i - 1) / block_size + 1;
    }

    cin >> total_queries;
    Query queries[MAX_N];
    for (int i = 1; i <= total_queries; i++) {
        cin >> queries[i].start >> queries[i].end;
        queries[i].idx = i;
    }

    sort(queries + 1, queries + total_queries + 1, cmp);

    int curL = 1, curR = 0;
    for (int i = 1; i <= total_queries; i++) {
        int L = queries[i].start, R = queries[i].end;
        while (curL < L) distinct_cnt -= (--freq[arr[curL++]] == 0);
        while (curL > L) distinct_cnt += (freq[arr[--curL]]++ == 0);
        while (curR < R) distinct_cnt += (freq[arr[++curR]]++ == 0);
        while (curR > R) distinct_cnt -= (--freq[arr[curR--]] == 0);
        result[queries[i].idx] = distinct_cnt;
    }

    for (int i = 1; i <= total_queries; i++) 
        cout << result[i] << " ";

    return 0;
}

데이터 업데이트가 필요한 경우 시간 차원을 추가합니다. 쿼리 구조체에 타임스탬프를 포함시키고, 블록 정렬 시 왼쪽 블록 → 오른쪽 블록 → 시간 순으로 정렬합니다. 블록 크기를 n²/³으로 설정하면 O(n⁵/³) 시간 복잡도를 달성할 수 있습니다.

struct Update {
    int pos, new_val;
};

struct Query {
    int start, end, time, idx;
};

bool cmp(Query a, Query b) {
    if (block[a.start] != block[b.start]) return a.start < b.start;
    if (block[a.end] != block[b.end]) return a.end < b.end;
    return a.time < b.time;
}

// 메인 루프 내 업데이트 처리
while (cur_time < query_time) {
    cur_time++;
    if (updates[cur_time].pos >= curL && updates[cur_time].pos <= curR) {
        distinct_cnt -= (--freq[arr[updates[cur_time].pos]] == 0);
        distinct_cnt += (freq[updates[cur_time].new_val]++ == 0);
    }
    swap(arr[updates[cur_time].pos], updates[cur_time].new_val);
}

트리 구조에 적용할 때는 오일러 투어를 이용합니다. 각 노드의 첫 번째(fir)와 두 번째(sec) 방문 순서를 기록합니다. u에서 v로의 경로 쿼리는 LCA를 기준으로 구간을 설정합니다. u가 LCA인 경우 [fir_u, fir_v], 아닌 경우 [sec_u, fir_v]를 사용하며, LCA를 별도로 처리합니다.

void process(int node) {
    visited[node] ? distinct_cnt -= !--freq[arr[node]] : distinct_cnt += !freq[arr[node]]++;
    visited[node] ^= 1;
}

// 쿼리 구간 설정
if (lca == u) 
    q[i] = {fir[u], fir[v], 0, i};
else 
    q[i] = {sec[u], fir[v], lca, i};

// LCA 처리
if (q[i].lca) process(q[i].lca);
result[q[i].idx] = distinct_cnt;
if (q[i].lca) process(q[i].lca);

가감성이 아닌 최댓값 연산과 같은 경우 롤백 모스를 사용합니다. 블록 내에서 왼쪽 포인터를 블록 끝으로 초기화하고 확장만 허용합니다. 블록 내 쿼리는 직접 계산하며, 오른쪽 포인터 이동은 이전 결과를 활용합니다.

for (int block_id = 1; block_id <= total_blocks; block_id++) {
    int left_start = block_end[block_id] + 1;
    int right_end = block_end[block_id];
    long long max_val = 0;
    memset(freq, 0, sizeof(freq));

    while (queries[idx].left_block == block_id) {
        if (same_block) {
            // 블록 내 직접 계산
            for (int k = ql; k <= qr; k++) 
                max_val = max(max_val, 1LL * data[k] * ++temp_freq[arr[k]]);
        } else {
            // 오른쪽 확장
            while (right_end < qr) 
                max_val = max(max_val, 1LL * data[++right_end] * ++freq[arr[right_end]]);
            long long temp_max = max_val;
            // 왼쪽 확장 (롤백)
            while (cur_left > ql) 
                max_val = max(max_val, 1LL * data[--cur_left] * ++freq[arr[cur_left]]);
            result[query.idx] = max_val;
            // 왼쪽 롤백
            while (cur_left < left_start) 
                --freq[arr[cur_left++]];
            max_val = temp_max;
        }
    }
}