Luogu P6587 시퀀스 최적화

제약 조건 \(x \le 20\) 활용, ID의 하위 \(x\) 비트를 Trie 구조와 세그먼트 트리 기법으로 처리

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int MAX_NODES = 4e6 + 5, MAX_ELEMS = 2e5 + 5;

int elem_count, query_count, base_data[MAX_ELEMS];
int child_nodes[MAX_ELEMS*20][2], node_counter = 0;
ll node_sum[MAX_NODES], lazy_update[MAX_NODES];
int subtree_size[MAX_NODES];
ll last_answer = 0;

void add_element(int value, int identifier) {
    int current_node = 0, tree_index = 1;
    subtree_size[tree_index]++;
    node_sum[tree_index] += value;
    
    for(int bit_pos = 0; bit_pos < 20; bit_pos++) {
        bool bit_val = identifier & (1 << bit_pos);
        if(!child_nodes[current_node][bit_val]) 
            child_nodes[current_node][bit_val] = ++node_counter;
        current_node = child_nodes[current_node][bit_val];
        tree_index = (bit_val) ? (tree_index << 1 | 1) : (tree_index << 1);
        subtree_size[tree_index]++;
        node_sum[tree_index] += value;
    }
}

void propagate_lazy(int tree_index) {
    if(lazy_update[tree_index]) {
        node_sum[tree_index << 1] += lazy_update[tree_index] * subtree_size[tree_index << 1];
        node_sum[tree_index << 1 | 1] += lazy_update[tree_index] * subtree_size[tree_index << 1 | 1];
        lazy_update[tree_index << 1] += lazy_update[tree_index];
        lazy_update[tree_index << 1 | 1] += lazy_update[tree_index];
        lazy_update[tree_index] = 0;
    }
}

void range_update(int bit_depth, int pattern, ll increment) {
    int current_node = 0, tree_index = 1;
    for(int bit_pos = 0; bit_pos < bit_depth; bit_pos++) {
        bool bit_val = pattern & (1 << bit_pos);
        propagate_lazy(tree_index);
        if(!child_nodes[current_node][bit_val]) return;
        current_node = child_nodes[current_node][bit_val];
        tree_index = (bit_val) ? (tree_index << 1 | 1) : (tree_index << 1);
    }
    lazy_update[tree_index] += increment;
    int current_size = subtree_size[tree_index];
    while(tree_index) {
        node_sum[tree_index] += increment * current_size;
        tree_index >>= 1;
    }
}

ll query_range(int bit_depth, int pattern) {
    int current_node = 0, tree_index = 1;
    for(int bit_pos = 0; bit_pos < bit_depth; bit_pos++) {
        bool bit_val = pattern & (1 << bit_pos);
        propagate_lazy(tree_index);
        if(!child_nodes[current_node][bit_val]) return 0;
        current_node = child_nodes[current_node][bit_val];
        tree_index = (bit_val) ? (tree_index << 1 | 1) : (tree_index << 1);
    }
    return node_sum[tree_index];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> elem_count >> query_count;
    for(int i = 1; i <= elem_count; i++) {
        cin >> base_data[i];
        add_element(base_data[i], i);
    }
    while(query_count--) {
        int operation_type;
        cin >> operation_type;
        int effective_op = (last_answer + operation_type) % 2 + 1;
        if(effective_op == 1) {
            int bit_len, pattern, value;
            cin >> bit_len >> pattern >> value;
            range_update(bit_len, pattern, value);
        } else {
            int bit_len, pattern;
            cin >> bit_len >> pattern;
            last_answer = query_range(bit_len, pattern);
            cout << last_answer << '\n';
        }
    }
    return 0;
}

USACO Secret Message 처리

Trie를 이용한 접두사 매칭 및 카운팅 구현

#include<iostream>
#include<vector>
using namespace std;
const int MAX_MSGS = 1e4 + 5, MAX_NODES = 5e5 + 5;

int msg_count, query_count;
int trie[MAX_NODES][2], terminal_count[MAX_NODES];
int path_count[MAX_NODES], node_index = 0;

void store_message() {
    int bit_length, bit_val, current_node = 0;
    cin >> bit_length;
    while(bit_length--) {
        cin >> bit_val;
        if(!trie[current_node][bit_val]) 
            trie[current_node][bit_val] = ++node_index;
        path_count[current_node]++;
        current_node = trie[current_node][bit_val];
    }
    terminal_count[current_node]++;
}

int process_query() {
    int bit_length, bit_val, current_node = 0, result = 0;
    cin >> bit_length;
    for(int i = 0; i < bit_length; i++) {
        cin >> bit_val;
        if(!trie[current_node][bit_val]) {
            while(++i < bit_length) cin >> bit_val;
            return result;
        }
        current_node = trie[current_node][bit_val];
        result += terminal_count[current_node];
    }
    return result + path_count[current_node];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> msg_count >> query_count;
    while(msg_count--) store_message();
    while(query_count--) cout << process_query() << '\n';
    return 0;
}

CF817E 사령관 선택 문제

비트 Trie에서 조건적 탐색을 통한 카운팅

#include<iostream>
using namespace std;
const int BIT_DEPTH = 28, MAX_NODES = 1e7;
int query_total, trie[MAX_NODES][2], node_total = 0;
int node_count[MAX_NODES];

void trie_update(int value, int delta) {
    int current_node = 0;
    for(int pos = BIT_DEPTH - 1; pos >= 0; pos--) {
        bool bit_flag = value & (1 << pos);
        if(!trie[current_node][bit_flag]) 
            trie[current_node][bit_flag] = ++node_total;
        current_node = trie[current_node][bit_flag];
        node_count[current_node] += delta;
    }
}

int trie_query(int value, int limit) {
    int current_node = 0, result = 0;
    for(int pos = BIT_DEPTH - 1; pos >= 0; pos--) {
        bool value_bit = value & (1 << pos);
        bool limit_bit = limit & (1 << pos);
        if(limit_bit) {
            result += node_count[trie[current_node][value_bit]];
            if(!trie[current_node][!value_bit]) return result;
            current_node = trie[current_node][!value_bit];
        }
        else {
            if(!trie[current_node][value_bit]) return result;
            current_node = trie[current_node][value_bit];
        }
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> query_total;
    while(query_total--) {
        int operation, param;
        cin >> operation >> param;
        if(operation == 1) trie_update(param, 1);
        else if(operation == 2) trie_update(param, -1);
        else cout << trie_query(param, cin >> param, param) << '\n';
    }
    return 0;
}

CF842D 비트 반전 연산

계층적 비트 반전과 Trie 재구성을 통한 최소 Mex 계산

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_BITS = 21, MAX_NODES = 3e5 * MAX_BITS;
int elem_total, query_total;
int trie[MAX_NODES][2], node_count[MAX_NODES];
bool bit_flip[MAX_BITS];

void trie_insert(int value) {
    int current_node = 0;
    for(int pos = MAX_BITS - 1; pos >= 0; pos--) {
        bool bit_val = value & (1 << pos);
        if(!trie[current_node][bit_val])
            trie[current_node][bit_val] = ++node_index;
        current_node = trie[current_node][bit_val];
        node_count[current_node]++;
    }
}

int calculate_mex(int xor_val) {
    int current_node = 0, result = 0;
    for(int pos = MAX_BITS - 1; pos >= 0; pos--) {
        bool bit_val = xor_val & (1 << pos);
        bit_flip[pos] ^= bit_val;
        if(node_count[trie[current_node][bit_flip[pos]]] != (1 << pos)) {
            current_node = trie[current_node][bit_flip[pos]];
        } else {
            current_node = trie[current_node][!bit_flip[pos]];
            result |= (1 << pos);
        }
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> elem_total >> query_total;
    vector<int> dataset(elem_total);
    for(auto &elem : dataset) cin >> elem;
    sort(dataset.begin(), dataset.end());
    dataset.erase(unique(dataset.begin(), dataset.end()), dataset.end());
    for(int elem : dataset) trie_insert(elem);
    while(query_total--) {
        int xor_value;
        cin >> xor_value;
        cout << calculate_mex(xor_value) << '\n';
    }
    return 0;
}