문제 접근 방식

이 문제는 수정 가능한 모스(Mo's) 알고리즘을 적용해야 하는 동적 쿼리 문제이다. 주어진 수열에 대해 두 가지 연산을 처리해야 한다: 특정 위치의 값을 변경하는 갱신 연산과 구간 내 특정 값의 등장 횟수를 세는 질의 연산.

기본 알고리즘 설계

모스 알고리즘의 핵심은 쿼리를 적절히 정렬하여 포인터 이동 횟수를 최소화하는 것이다. 수정 가능한 버전에서는 시간 차원까지 고려해야 하므로 3차원으로 정렬한다.

inline void insert_value(int value) {
    occurrence_count[value]++;
}

inline void remove_value(int value) {
    occurrence_count[value]--;
}

// 현재 구간에서 특정 값의 빈도 반환
int get_frequency(int target_value) {
    return occurrence_count[target_value];
}

이산화 과정

값의 범위가 크기 때문에 이산화를 통해 메모리와 시간 복잡도를 줄인다. 입력된 모든 수열 원소와 갱신 작업에서 사용되는 값들을 수집하여 정렬하고 중복을 제거한다.

// 전체 가능한 값들 수집
vector<int> all_values;
for (int i = 1; i <= sequence_length; i++) {
    all_values.push_back(original_array[i]);
}
for (int i = 0; i < update_operations.size(); i++) {
    all_values.push_back(update_operations[i].new_value);
}

// 정렬 및 중복 제거
sort(all_values.begin(), all_values.end());
all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());

// 실제 배열과 쿼리 값들을 이산화
for (int i = 1; i <= sequence_length; i++) {
    original_array[i] = find_discretized_index(original_array[i]);
}
for (auto& query : queries) {
    query.target_value = find_discretized_index(query.target_value);
}

시간 복잡도 분석

수정 가능한 모스 알고리즘의 기본 복잡도는 O(n^(5/3))이며, 이산화 과정의 추가적인 O(n log n)이 더해진다. 블록 크기는 n^(2/3)로 설정하는 것이 일반적으로 최적이다.

구현 코드

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

const int MAX_SIZE = 1e5 + 10;
int block_size, sequence[MAX_SIZE];

struct Query {
    int left_pos, right_pos, target_val;
    int time_stamp, query_id;
};

struct Update {
    int position, new_value;
};

vector<Query> query_list;
vector<Update> update_list;
int frequency[MAX_SIZE * 2];
int result[MAX_SIZE];
vector<int> discretized_values;

bool compare_queries(const Query& a, const Query& b) {
    if (a.left_pos / block_size != b.left_pos / block_size) {
        return a.left_pos / block_size < b.left_pos / block_size;
    }
    if (a.right_pos / block_size != b.right_pos / block_size) {
        return a.right_pos / block_size < b.right_pos / block_size;
    }
    return a.time_stamp < b.time_stamp;
}

int find_index(int value) {
    return lower_bound(discretized_values.begin(), discretized_values.end(), value) 
           - discretized_values.begin() + 1;
}

void apply_addition(int pos) {
    frequency[sequence[pos]]++;
}

void apply_removal(int pos) {
    frequency[sequence[pos]]--;
}

void process_update(int query_left, int query_right, int update_idx) {
    auto& update_op = update_list[update_idx];
    if (query_left <= update_op.position && update_op.position <= query_right) {
        apply_removal(update_op.position);
        int temp = sequence[update_op.position];
        sequence[update_op.position] = update_op.new_value;
        apply_addition(update_op.position);
        update_op.new_value = temp;
    } else {
        swap(sequence[update_op.position], update_op.new_value);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> raw_input(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> raw_input[i];
        discretized_values.push_back(raw_input[i]);
        sequence[i] = raw_input[i];
    }
    
    block_size = cbrt(n * n) + 1;
    
    for (int i = 0; i < m; i++) {
        char operation_type;
        cin >> operation_type;
        
        if (operation_type == 'Q') {
            int l, r, k;
            cin >> l >> r >> k;
            discretized_values.push_back(k);
            query_list.push_back({l, r, k, (int)update_list.size(), (int)query_list.size()});
        } else {
            int pos, val;
            cin >> pos >> val;
            discretized_values.push_back(val);
            update_list.push_back({pos, val});
        }
    }
    
    sort(discretized_values.begin(), discretized_values.end());
    discretized_values.erase(unique(discretized_values.begin(), discretized_values.end()), 
                            discretized_values.end());
    
    for (int i = 1; i <= n; i++) {
        sequence[i] = find_index(sequence[i]);
    }
    
    for (auto& q : query_list) {
        q.target_val = find_index(q.target_val);
    }
    
    for (auto& u : update_list) {
        u.new_value = find_index(u.new_value);
    }
    
    sort(query_list.begin(), query_list.end(), compare_queries);
    
    int current_left = 1, current_right = 0, current_time = 0;
    
    for (const auto& q : query_list) {
        while (current_left < q.left_pos) {
            apply_removal(current_left++);
        }
        while (current_left > q.left_pos) {
            apply_addition(--current_left);
        }
        while (current_right < q.right_pos) {
            apply_addition(++current_right);
        }
        while (current_right > q.right_pos) {
            apply_removal(current_right--);
        }
        while (current_time < q.time_stamp) {
            process_update(q.left_pos, q.right_pos, current_time++);
        }
        while (current_time > q.time_stamp) {
            process_update(q.left_pos, q.right_pos, --current_time);
        }
        
        result[q.query_id] = frequency[q.target_val];
    }
    
    for (int i = 0; i < query_list.size(); i++) {
        cout << result[i] << "\n";
    }
    
    return 0;
}

이 구현은 수정 가능한 모스 알고리즘의 전형적인 패턴을 따르면서도 이산화를 통한 최적화를 적용하여 대규모 입력에서도 효율적으로 작동한다.