And mex#11807

And mex (Həll təhlili)

Problem Müəllifi:	Kostiantyn Denysov
Hazırlayan:	Maksym Shvedchenko
Redaktə edən:	Maksym Shvedchenko

Başlamaq üçün kiçik bir fakt: əgər bir $x$ ədədinin $S$ -də olub-olmadığını yoxlamaq istəyiriksə, $x$ ədədinin bütün supermaskalarını götürüb onların $A N D$ -ının $x$ -ə bərabər olub-olmadığını yoxlaya bilərik. Bunun niyə optimal olduğunu sübut etməyi oxucuya bir məşq olaraq buraxırıq.

Biz $d p_{ma s k}$ dp_{mask}-ı saxlayacağıq, bu da bütün supermaskaların $A N D$ -ını hesablamaq üçün istifadə ediləcəkdir. Əlavələr olmadan bu, SOS DP istifadə edilərək $O (k 2^{k})$ O(k2^k) zaman mürəkkəbliyində edilə bilər. Burada $k$ elə kiçik iki ədədin qüvvətidir ki, $max_{1 \leq i \leq n} a_{i} < 2^{k}$ \max_{1 \leq i \leq n} a_i < 2^k olur.

İndi elementləri necə əlavə edəcəyimizi anlamağa çalışaq. $y$ əlavə etsək, $d p$ -də dəyişə biləcək tək dəyərlər $y$ -in submaskalarıdır. Onları sadə şəkildə təkrar etmək $3^{k}$ 3^k zaman mürəkkəbliyinə səbəb olur (çünki eyni ədədi təkrarən emal etmək üçün heç bir səbəb yoxdur), bu isə çox yavaşdır. Eyni ədədi təkrarən emal etməmək ideyasını təkmilləşdirək. Əgər artıq $d p_{y} = y$ dp_y = y olursa, o halda onun heç bir submaskasını emal etməyə ehtiyac yoxdur, çünki $y$ artıq əldə edilə bilər. Bənzər şəkildə, əgər $y^{'}$ y' hansısa bir submaskada $d p_{y^{'}} = y^{'}$ dp_{y'} = y'-ə sahib olursa, o zaman $y^{'}$ y'-in submaskalarını təkrarlamağa ehtiyac yoxdur.

Daha çox düşündüyümüzdə, əgər $d p_{y^{'}}$ dp_{y'} dəyəri $y^{'}$ y' subsmaskasında $y$ istifadə etdikdən sonra dəyişməz qalırsa, o halda $y^{'}$ y' bu submaskalara keçməyə dəyməz. Beləliklə, submaskaları gəzərkən erkən dayana biləcək effektiv bir yol tapmalıyıq. Bunun üçün BFS istifadə edəcəyik. $y$ nodundan başlayırıq və hər addımda bir biti söndürürük. Əgər $d p_{y^{'}} u 0026 y = d p_{y^{'}}$ dp_{y'} \\u0026 y = dp_{y'} olursa, dayandırırıq. Bu şəkildə, hər bir nod ən çox $k$ dəfə rahatlayır, ən pis halda $k^{2}$ k^2 əməliyyat keçirən $2^{k}$ 2^k nod vardır. Beləliklə, $O (k^{2} 2^{k})$ O(k^2 2^k) mürəkkəblik əldə edilir.

#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))
#define rep(i, n) for(int i = 0; i < (n); i++)

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, m;
    cin >> n >> m;
    vec<int> a(n);
    cin >> a;
    vec<int> b(m);
    cin >> b;
    int C = 20;
    vec<int> dp(pow2(C) + 1, (1 << 21) - 1);
    queue<int> q;
    auto insert = [&](int x) {
        q.push(x);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if ((dp[u] & x) == dp[u]) continue;
            dp[u] &= x;
            int t = u;
            while (t) {
                int bit = low_bit(t);
                q.push(u ^ bit);
                t -= bit;
            }
        }
    };

    int MEX = 0;
    for (auto x: a) {
        insert(x);
    }
    while (MEX < len(dp) && dp[MEX] == MEX) MEX++;
    cout << MEX << " ";
    for (auto x: b) {
        insert(x);
        while (MEX < len(dp) && dp[MEX] == MEX) MEX++;
        cout << MEX << " ";
    }
}

C++