2023-05-15

AOJ 3333 Range Xor Query (HUPC 2023 day1-J)

AOJ 有志コン HUPC クエリ処理問題数列平方分割 XOR BinaryTrie データ構造区間クエリ:区間操作:区間操作:上書き

Binary Trie + 平方分割

問題概要

数列 $A_{1}, A_{2}, \dots, A_{N}$ に対して、以下の $Q$ 個のクエリを処理せよ。

クエリタイプ 1 (k x)： $A_{k}$ を $A_{k}$ xor $x$ に置き換える
クエリタイプ 2 (l r x)： $\displaystyle \min_{l \le i \le r} (A_{i}$ xor $x)$ の値を出力する

制約

$1 \le N, Q \le 2 \times 10^{5}$
$1 \le A_{i}, x \le 1000$

考えたこと

これは TL で解法を見た上で解いた。

$x$ との xor を一斉にとって最小値を求めるといえば、Binary Trie が思い浮かぶ。

しかし Binary Trie ができることは「それに含まれる値すべてに $x$ との xor をとって得られる値たちの最小値」を求めることだ。今のままでは難しいので、数列を平方分割する。

数列を平方分割して、各バケットに、そのバケットの値をすべて管理する Binary Trie を乗せる。そして、クエリタイプ 2 の処理は、

端っこの処理：素直に $A_{i}$ xor $x$ を計算する
各バケットの処理：Binary Trie の get_min(x) を使う

というようにすればよい。

バケットサイズは、登場する値の最大値を $M$ として $O(\sqrt{N \log{M}})$ とするのがよい。

このとき計算量は、 $O(Q\sqrt{N \log{M}})$ となる。

コード

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

// Binary Trie
template<typename INT, size_t MAX_DIGIT> struct BinaryTrie {
    struct Node {
        size_t count;
        Node *prev, *left, *right;
        Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}
    };
    INT lazy;
    Node *root;

    // constructor
    BinaryTrie() : lazy(0), root(emplace(nullptr)) {}
    inline size_t get_count(Node *v) const { return v ? v->count : 0; }
    inline size_t size() const { return get_count(root); }

    // add and get value of Node
    inline void add(INT val) {
        lazy ^= val;
    }
    inline INT get(Node *v) {
        if (!v) return -1;
        INT res = 0;
        for (int i = 0; i < MAX_DIGIT; ++i) {
            if (v == v->prev->right)
                res |= INT(1)<<i;
            v = v->prev;
        }
        return res ^ lazy;
    }

    // find Node* whose value is val
    Node* find(INT val) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag) v = v->right;
            else v = v->left;
            if (!v) return v;
        }
        return v;
    }

    // insert
    inline Node* emplace(Node *prev) {
        return new Node(prev);
    }
    void insert(INT val, size_t k = 1) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag && !v->right) v->right = emplace(v);
            if (!flag && !v->left) v->left = emplace(v);
            if (flag) v = v->right;
            else v = v->left;
        }
        v->count += k;
        while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right);
    }
    
    // erase
    Node* clear(Node *v) {
        if (!v || get_count(v)) return v;
        delete(v);
        return nullptr;
    }
    bool erase(Node *v, size_t k = 1) {
        if (!v) return false;
        v->count -= k;
        while ((v = v->prev)) {
            v->left = clear(v->left);
            v->right = clear(v->right);
            v->count = get_count(v->left) + get_count(v->right);
        }
        return true;
    }
    bool erase(INT val) {
        auto v = find(val);
        return erase(v);
    }

    // max (with xor-addition of val) and min (with xor-addition of val)
    Node* get_max(INT val = 0) {
        INT nval = val ^ lazy;
        Node* v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (!v->right) v = v->left;
            else if (!v->left) v = v->right;
            else if (flag) v = v->left;
            else v = v->right;
        }
        return v;
    }
    Node* get_min(INT val = 0) {
        return get_max(~val & ((INT(1)<<MAX_DIGIT)-1));
    }
   
    // lower_bound, upper_bound
    Node* get_cur_node(Node *v, int i) {
        if (!v) return v;
        Node *left = v->left, *right = v->right;
        if ((lazy >> i) & 1) swap(left, right);
        if (left) return get_cur_node(left, i+1);
        else if (right) return get_cur_node(right, i+1);
        return v;
    }
    Node* get_next_node(Node *v, int i) {
        if (!v->prev) return nullptr;
        Node *left = v->prev->left, *right = v->prev->right;
        if ((lazy >> (i+1)) & 1) swap(left, right);
        if (v == left && right) return get_cur_node(right, i);
        else return get_next_node(v->prev, i+1);
    }
    Node* lower_bound(INT val) {
        INT nval = val ^ lazy;
        Node *v = root;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (nval >> i) & 1;
            if (flag && v->right) v = v->right;
            else if (!flag && v->left) v = v->left;
            else if ((val >> i) & 1) return get_next_node(v, i);
            else return get_cur_node(v, i);
        }
        return v;
    }
    Node* upper_bound(INT val) {
        return lower_bound(val + 1);
    }
    size_t order_of_val(INT val) {
        Node *v = root;
        size_t res = 0;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            Node *left = v->left, *right = v->right;
            if ((lazy >> i) & 1) swap(left, right);
            bool flag = (val >> i) & 1;
            if (flag) {
                res += get_count(left);
                v = right;
            }
            else v = left;
        }
        return res;
    }

    // k-th, k is 0-indexed
    Node* get_kth(size_t k, INT val = 0) {
        Node *v = root;
        if (get_count(v) <= k) return nullptr;
        for (int i = MAX_DIGIT-1; i >= 0; --i) {
            bool flag = (lazy >> i) & 1;
            Node *left = (flag ? v->right : v->left);
            Node *right = (flag ? v->left : v->right);
            if (get_count(left) <= k) k -= get_count(left), v = right;
            else v = left;
        }
        return v;
    }

    // debug
    void print(Node *v, string prefix = "") {
        if (!v) return;
        cout << prefix << ": " << v->count << endl;
        print(v->left, prefix + "0");
        print(v->right, prefix + "1");
    }
    void print() {
        print(root);
    }
    vector<INT> eval(Node *v, int digit) const {
        vector<INT> res;
        if (!v) return res;
        if (!v->left && !v->right) {
            for (int i = 0; i < get_count(v); ++i) res.push_back(0);
            return res;
        }
        const auto& left = eval(v->left, digit-1);
        const auto& right = eval(v->right, digit-1);
        for (auto val : left) res.push_back(val);
        for (auto val : right) res.push_back(val + (INT(1)<<digit));
        return res;
    }
    vector<INT> eval() const {
        auto res = eval(root, MAX_DIGIT-1);
        for (auto &val : res) val ^= lazy;
        return res;
    }
    friend ostream& operator << (ostream &os,
                                 const BinaryTrie<INT, MAX_DIGIT> &bt) {
        auto res = bt.eval();
        for (auto val : res) os << val << " ";
        return os;
    }
};

void AOJ3333() {
    const int width = 2000;
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    vector<BinaryTrie<int,12>> vbt(N/width + 1);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        vbt[i / width].insert(A[i]);
    }
    
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k, x;
            cin >> k >> x;
            --k;
            vbt[k / width].erase(A[k]);
            A[k] ^= x;
            vbt[k / width].insert(A[k]);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            --l;
            int res = 1<<29;
            int iter = l;
            while (iter < r && iter % width != 0) {
                res = min(res, A[iter] ^ x);
                ++iter;
            }
            while (iter + width <= r) {
                int tmp = vbt[iter / width].get(vbt[iter / width].get_min(x)) ^ x;
                res = min(res, tmp);
                iter += width;
            }
            while (iter < r) {
                res = min(res, A[iter] ^ x);
                ++iter;
            }
            cout << res << endl;
        }
    }
}

int main() {
    AOJ3333();
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3333 Range Xor Query (HUPC 2023 day1-J)

問題概要

制約

考えたこと

コード