Battle#11768
Problem Author: | Illia Shevchenko |
Prepared by: | Maksym Shvedchenko Illia Shevchenko |
Editorial by: | Maksym Shvedchenko |
To begin, let's solve a simpler problem: we need a data structure in which we can add and remove numbers and find the MEX of the set. To achieve this, we will maintain a bit trie of the numbers. To find the MEX using the trie, we will also keep track of the sizes of the subtrees. We start with the most significant bits; if the subtree with bit is complete, then this bit in the MEX is , otherwise it is . We then recursively solve the problem for the necessary subtree.
Now, if we can XOR with any number, by performing the same approach, we will simply check whether we want to swap the subtrees (if one of them is complete). If there are no complete subtrees, we recursively check both subtrees (which is slow, so we will store this value as DP).
When we have a limiter, we can do the same, with one exception: recalculation will have to be done each time. However, the key idea is that if the current bit of the limiter is , we can recursively proceed to only one node. Otherwise, we choose one of the subtrees where the bit does not need to be recalculated since we are not using the bit, which is relatively easy to implement (carefully writing several ifs is necessary).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report \
auto end = std::chrono::high_resolution_clock::now(); \
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
{ cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
using hashmap = gp_hash_table<int, int, custom_hash>;
template<typename T>
vector<T> vect(int n, T val) {
return vector<T>(n, val);
}
template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
return vector<vector<T>>(n, vector<T>(m, val));
}
template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}
template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}
template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
return matrix<T>(n, vector<T>(m, val));
}
template<typename T>
graph<T> new_graph(int n) {
return graph<T>(n);
}
template<class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template<class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;
template<typename T>
using vec = vector<T>;
using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;
template<typename T>
istream &operator>>(istream &is, vec<T> &v) {
for (int &x: v) is >> x;
return is;
}
template<typename T>
ostream &operator<<(ostream &os, const vec<T> &v) {
for (int i = 0; i < len(v); i++) {
if (i) os << " ";
os << v[i];
}
return os;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vec<int> a(n);
cin >> a;
vec<int> y(n);
cin >> y;
set<int> used;
int LOG = 30;
struct node {
node *next[2];
int bt;
int cnt = 0;
int dp = 0;
int min_xor;
};
node *root = new node();
root->bt = LOG - 1;
root->next[0] = root->next[1] = nullptr;
auto insert = [&](int x) {
if (used.count(x)) return;
used.insert(x);
function<void(node *)> add = [&](node *cur) {
if (cur->bt == -1) {
cur->cnt++;
cur->dp = 1;
cur->min_xor = 0;
return;
}
int b = bit(x, cur->bt);
if (cur->next[b] == nullptr) {
cur->next[b] = new node();
cur->next[b]->bt = cur->bt - 1;
cur->next[b]->next[0] = cur->next[b]->next[1] = nullptr;
}
add(cur->next[b]);
cur->cnt = 0;
int c0 = 0;
int c1 = 0;
int d0 = 0;
int d1 = 0;
int x0 = 0;
int x1 = 0;
if (cur->next[0] != nullptr) c0 += cur->next[0]->cnt, d0 = cur->next[0]->dp, x0 = cur->next[0]->min_xor;
if (cur->next[1] != nullptr) c1 += cur->next[1]->cnt, d1 = cur->next[1]->dp, x1 = cur->next[1]->min_xor;
cur->cnt = c0 + c1;
if (c0 == pow2(cur->bt)) {
cur->dp = pow2(cur->bt) + d1;
cur->min_xor = x1;
} elif (c1 == pow2(cur->bt)) {
cur->dp = pow2(cur->bt) + d0;
cur->min_xor = x0;
cur->min_xor = set_bit(cur->min_xor, cur->bt);
} else {
if (d0 >= d1) {
cur->dp = d0;
cur->min_xor = x0;
} else {
cur->dp = d1;
cur->min_xor = x1;
cur->min_xor = set_bit(cur->min_xor, cur->bt);
}
}
};
add(root);
};
auto best_MEX = [&](int Y) {
function<pair<int, int>(node *, int)> dfs = [&](node *cur, int brd) -> pII {
if (cur == nullptr) return {0, 0};
if (cur->min_xor <= brd) {
return {cur->dp, cur->min_xor};
}
int c0 = 0;
int c1 = 0;
if (cur->next[0] != nullptr) c0 += cur->next[0]->cnt;
if (cur->next[1] != nullptr) c1 += cur->next[1]->cnt;
if (!bit(brd, cur->bt)) {
if (c0 == pow2(cur->bt)) {
auto [k, t] = dfs(cur->next[1], brd);
return {pow2(cur->bt) + k, t};
} else {
return dfs(cur->next[0], brd);
}
} else {
if (c0 == pow2(cur->bt)) {
auto [k, t] = dfs(cur->next[1], clear_bit(brd, cur->bt));
return {pow2(cur->bt) + k, t};
} elif (c1 == pow2(cur->bt)) {
auto [k, t] = dfs(cur->next[0], clear_bit(brd, cur->bt));
return {pow2(cur->bt) + k, t};
} else {
auto [k0, t0] = dfs(cur->next[0], inf);
auto [k1, t1] = dfs(cur->next[1], clear_bit(brd, cur->bt));
if (k0 >= k1) {
return {k0, t0};
} else {
return {k1, t1};
}
}
}
};
auto [k, t] = dfs(root, Y);
return k;
};
for (int i = 0; i < n; i++) {
insert(a[i]);
cout << best_MEX(y[i]) << " ";
}
}