[C++]白準16903号:数列とクエリー20

質問リンク

16903号:数列とクエリー20

問題の概要

0を含む配列Aの場合、次のクエリが実行されます.
1 x:Aにxを加える.
2 x:Aからxを削除します.Aにxが2つ以上ある場合は、1つだけ削除します.常にAにxのあるクエリーのみが与えられます.
3 x:Aの各要素とxについてXOR演算を行い、最大値を出力します.

方法

1回のクエリの場合、xをビットセットに置き換え、trieに保存します.ストライプ内の各ノードには、0と1の2ビットのサブノードを指すポインタ変数があります.また、cnt変数を使用して、現在のノードの対応する数を格納することもできます.ブラケットでは、必要に応じてノードを作成し、アクセスするたびにcnt変数を追加できます.
削除するときは、逆にできます.cntが減少すると、ノードが0になった場合、delete演算子を使用して削除されます.削除ノードの親ノードは、NULLをポインタ変数に置き換えます.
3番目のクエリーです.XORは2つの異なるビット間で1になる必要があります.XOR値を最大化するには、2つの対応するビットができるだけ異なる必要があります.xをビットセットに置き換え、サブノードをストリップのルートからxの現在のビットに対応する別のビットに移動します.そうでない場合は、同じビットのノードに移動します.リフトに達すると、2つのXOR値が返されて出力されます.
0はすでに配列中であることに注意してください.
解が終わった後,難易度の寄与によりセグメントツリーを用いて解くことができるが,セグメントツリーを用いて解く方法はまだ考えられていない.もしあなたが思いついたら、私はそれをここに追加したいです.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	int cnt;
	Trie* node[2];

	Trie() {
		cnt = 0;
		node[0] = node[1] = NULL;
	}

	void insert(bitset<32>& bit, int idx) {
		cnt++;

		if (idx == -1)
			return;

		if (node[bit[idx]] == NULL) {
			Trie* trie = new Trie();
			node[bit[idx]] = trie;
		}

		node[bit[idx]]->insert(bit, idx - 1);
	}

	void erase(bitset<32>& bit, int idx) {
		cnt--;

		if (idx == -1)
			return;
		
		node[bit[idx]]->erase(bit, idx - 1);

		if (!node[bit[idx]]->cnt) {
			delete node[bit[idx]];
			node[bit[idx]] = NULL;
		}
	}

	int find(bitset<32>& bit, bitset<32>& res, int idx) {
		if (idx == -1)
			return (int)res.to_ulong();

		if (node[!bit[idx]] != NULL) {
			res[idx] = 1;
			return node[!bit[idx]]->find(bit, res, idx - 1);
		}
		else {
			res[idx] = 0;
			return node[bit[idx]]->find(bit, res, idx - 1);
		}
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int m;
	cin >> m;

	Trie* root = new Trie();
	bitset<32> zero(0);
	root->insert(zero, 31);

	while (m--) {
		int q, x;
		cin >> q >> x;

		bitset<32> tmp(x);
		bitset<32> res(x);

		switch (q) {
		case 1:
			root->insert(tmp, 31);
			break;
		case 2:
			root->erase(tmp, 31);
			break;
		case 3:
			cout << root->find(tmp, res, 31) << '\n';
		}
	}

	delete root;
	return 0;
}