test/binary-search-tree/BinaryTrie-set-xor-min.test.cpp

View this file on GitHub
Last update: 2023-06-14 01:56:03+09:00
Problem: https://judge.yosupo.jp/problem/set_xor_min

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/set_xor_min"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#include "../../lib/12-binary-search-tree/BinaryTrie.cpp"
#include "../../lib/99-operator/monoid/MonoidRangeSumPointAdd.cpp"
int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	BinaryTrie<MonoidRangeSumPointAdd<int>,30> trie;
	int Q; cin >> Q;
	while (Q--){
		int q; cin >> q;
		long long x; cin >> x;
		if(q==0) {
			long long y=trie.fold(x);
			if(!y) trie.operate(x,1);
		}
		if(q==1) {
			long long y=trie.fold(x);
			if(y) trie.operate(x,-1);
		}
		if(q==2) {
			cout << trie.min_bitwise_xor(x) << endl;
		}
	}
}

#line 1 "test/binary-search-tree/BinaryTrie-set-xor-min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/set_xor_min"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#line 1 "lib/12-binary-search-tree/BinaryTrie.cpp"
/*
 * @title BinaryTrie
 * @docs md/12-binary-search-tree/BinaryTrie.md
 */
template<class Operator, int bit=60> class BinaryTrie{
    using TypeNode = typename Operator::TypeNode;
public:
    vector<TypeNode> node;
    vector<vector<int>> ch;
    BinaryTrie():node(1),ch(1,vector<int>(2,-1)){}
    void operate(long long idx, const TypeNode var) {
        int curr=0;
        stack<int> st;
        for(int i=bit-1; 0 <= i; --i) {
            st.push(curr);
            int f=(idx>>i)&1;
            if(ch[curr][f]==-1) {
                node.push_back(Operator::unit_node);
                ch.push_back(vector<int>(2,-1));
                ch[curr][f] = (int)node.size()-1;
            }
            curr = ch[curr][f];
        }
        node[curr] = Operator::func_operate(node[curr],var);
        while(st.size()) {
            curr = st.top(); st.pop();
            node[curr]=Operator::unit_node;
            if(ch[curr][0]!=-1)	node[curr] = Operator::func_fold(node[ch[curr][0]],node[curr]);
            if(ch[curr][1]!=-1)	node[curr] = Operator::func_fold(node[curr],node[ch[curr][1]]);
        }
    }
    TypeNode fold(long long idx) {
        int curr=0;
        for(int i=bit-1; 0 <= i; --i) {
            int f=(idx>>i)&1;
            if(ch[curr][f]!=-1) curr = ch[curr][f];
            else return Operator::unit_node;
        }
        return node[curr];
    }
    long long min_bitwise_xor(long long x) {
        int curr=0;
        long long y=0;
        for(int i=bit-1; 0 <= i; --i) {
            long long f=(x>>i)&1;
            if(!node[curr]) break;
            if(ch[curr][f]!=-1 && node[ch[curr][f]]) curr = ch[curr][f];
            else curr = ch[curr][f^=1];
            y^=(f<<i);
        }
        return y^x;
    }
};
#line 1 "lib/99-operator/monoid/MonoidRangeSumPointAdd.cpp"
/*
 * @title MonoidRangeSumPointAdd - [区間和, 一点加算]
 * @docs md/operator/monoid/MonoidRangeSumPointAdd.md
 */
template<class T> struct MonoidRangeSumPointAdd {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_fold(TypeNode l,TypeNode r){return l+r;}
    inline static constexpr TypeNode func_operate(TypeNode l,TypeNode r){return l+r;}
    inline static constexpr bool func_check(TypeNode nodeVal,TypeNode var){return var == nodeVal;}
};
#line 9 "test/binary-search-tree/BinaryTrie-set-xor-min.test.cpp"
int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	BinaryTrie<MonoidRangeSumPointAdd<int>,30> trie;
	int Q; cin >> Q;
	while (Q--){
		int q; cin >> q;
		long long x; cin >> x;
		if(q==0) {
			long long y=trie.fold(x);
			if(!y) trie.operate(x,1);
		}
		if(q==1) {
			long long y=trie.fold(x);
			if(y) trie.operate(x,-1);
		}
		if(q==2) {
			cout << trie.min_bitwise_xor(x) << endl;
		}
	}
}