XOR базис з видаленнями

Передмова

Ця стаття використовує терміни лінійної алгебри. Якщо ви їх розумієте, можете пропустити цей розділ.

Ціле число між $0$ (включно) і $2^{m}$ 2^m (не включно) можна розглядати як $m$ -вимірний вектор, беручи до уваги його бінарне представлення. Операція обчислення $xor$ (виключне АБО) відповідає знаходженню суми кожного елемента за модулем $2$ , а операція вибору деяких елементів з набору цілих чисел і знаходження їх $xor$ відповідає множенню на $0$ або $1$ для векторів і складанню їх за модулем $2$ . Сума кількох добутків скаляра і вектора називається лінійною комбінацією.

$span (X)$ позначає множину всіх можливих $xor$ -ів деяких елементів множини $X$ . Наприклад, $span ({1, 2, 4}) = {0, 1, 2, 4, 1 \oplus 2, 1 \oplus 4, 2 \oplus 4, 1 \oplus 2 \oplus 4} = {0, 1, 2, 3, 4, 5, 6, 7}$ \operatorname{span}(\{1, 2, 4\})=\{0, 1, 2, 4, 1 \oplus 2, 1 \oplus 4, 2 \oplus 4, 1 \oplus 2 \oplus 4 \} = \{0, 1, 2, 3, 4, 5, 6, 7 \} ( $xor$ порожньої множини дорівнює $0$ ).

Вступ

Згадаємо таку відому задачу:

Детальніше про те як розв'язувати цю задачу можна дізнатися за посиланням.

В цій статті будемо розглядати більш складну задачу, де ще є запити видалення числа з множини $S$ . Крім того, ми отримуємо наступний запит, тільки після того, як відповіли на попередній (тобто задачу треба розв'язувати "в онлайні").

Початкову задачу можна розв'язувати за $O (m)$ на запит, а от задачу з видаленнями будемо навчатися розв'язувати за $O (m^{2})$ O(m^2).

Структура

У задачі з видаленнями в нас починаються невизначеності на моменті, коли число, що ми додаємо до XOR базису представляється $xor$ -ами наявних чисел.

Ми хочемо ефективно зберегти кожне число, що додається до $S$ , тому будемо підтримувати послідовність $X_{n} (n \geq 1)$ X_n (n \ge 1) XOR базисів (кожен з яких є початково порожнім), замість одного базису.

Додавання числа $v$ до $S$

Розглянемо як саме будемо додавати нове число $v \neq = 0$ v \neq 0 до множини $S$ :

Будемо поступово обходити по нашим базисами починаючи з першого. Нехай $i$ — номер поточного базису, який розглядаємо;
Якщо $v \in / span (X_{i})$ v \notin \operatorname{span}(X_i), то просто додамо $v$ до $X_{i}$ X_i і закінчимо процедуру;
Інакше, $v \in span (X_{i})$ v \in \operatorname{span}(X_i), то так додати не виходить, але ми прагнемо обов'язково десь зберегти це число. Тому збільшуємо $i$ на $1$ та повертаємося до кроку $2$ .

Іншими словами, ми знаходимо таке мінімальне $i$ , що $v \in / span (X_{i})$ v \notin \operatorname{span}(X_i) та додаємо $v$ до $X_{i}$ X_i. Якщо в лоб реалізувати цей алгоритм, то в гіршому випадку він буде працювати за $O (∣ S ∣)$ , що досить неефективно.

Будемо покращувати цей алгоритм. Спершу розглянемо деякі властивості даної послідовності базисів $X_{n}$ X_n:

Використовуючи ці дві властивості можна покращити алгоритм, щоб додавання працювало за $O (m^{2})$ O(m^2) або навіть $O (m lo g m)$ O(m \log{m}).

Нагадаємо, що ми знаходимо таке мінімальне $i$ , що $v \in / span (X_{i})$ v \notin \operatorname{span}(X_i) та додаємо $v$ до $X_{i}$ X_i. Оскільки унікальних $span (X_{i})$ \operatorname{span}(X_i) не більше $m + 1$ m+1, то треба лише перебирати ті $i$ , для яких $i = 1$ i=1 або $span (X_{i}) \neq = span (X_{i - 1})$ \operatorname{span}(X_i) \neq \operatorname{span}(X_{i-1}). Тоді досягнемо складності $O (m^{2})$ O(m^2). Якщо використати бінарний пошук по цим індексам $i$ , то досягнемо складності $O (m lo g m)$ O(m \log m).

Отже, ми навчилися додавати число $v \neq = 0$ v \neq 0 до множини $S$ .

Видалення числа $v \in S$ v \in S

Оберемо $j$ , так що $v \in X_{j}$ v \in X_j. Якщо просто видалити $v$ з $X_{j}$ X_j, то порушаться властивості, що зазначили попередньо. Ми будемо прагнути, щоб ці властивості виконувались після видалення.

Будемо видаляти таким чином:

Поки $span (X_{j}) = span (X_{j + 1})$ \operatorname{span}(X_j)=\operatorname{span}(X_{j+1}), то міняємо місцями базиси $X_{j}$ X_j та $X_{j + 1}$ X_{j+1} ( $swap (X_{j}, X_{j + 1})$ \operatorname{swap}(X_j, X_{j+1})) та збільшуємо $j$ на $1$ . Оскільки $span (X_{j}) = span (X_{j + 1})$ \operatorname{span}(X_j)=\operatorname{span}(X_{j+1}), то неважливо в якому порядку розташовані ці базиси у послідовності, тому можна довільно їх перемішувати;
Тепер $span (X_{j}) \neq = span (X_{j + 1})$ \operatorname{span}(X_j) \neq \operatorname{span}(X_{j+1}). Маємо два випадки:
1. $span (X_{j} ∖ {v}) \supseteq span (X_{j + 1})$ \operatorname{span}(X_j \setminus \{v\}) \supseteq \operatorname{span}(X_{j+1}). В цьому випадку можемо просто видалити число $v$ з $X_{j}$ X_j та закінчити процедуру;
2. $span (X_{j} ∖ {v}) ⊉ span (X_{j + 1})$ \operatorname{span}(X_j \setminus \{v\}) \nsupseteq \operatorname{span}(X_{j+1}). Розглянемо одне твердження:
  Твердження 1
  $\exists y \in X_{j + 1} : span ((X_{j} ∖ {v}) \cup y) = span (X_{j})$ \exist y \in X_{j+1}: \operatorname{span}((X_j \setminus \{v\}) \cup y)=\operatorname{span}(X_j).
  Знайдемо цей $y \in X_{j + 1}$ y \in X_{j+1} з твердження. Тоді можемо замінити $v$ у $X_{j}$ X_j на $y$ і тепер продовжити процедуру з кроку $1$ , але тепер ми будемо видаляти вже число $y$ з множини $X_{j + 1}$ X_{j+1}.

Проаналізуємо часову складність процедури видалення. Скільки разів ми будемо попадати у випадок $2.2$ ? Нескладно зрозуміти, що не більше $m$ разів, оскільки кожен раз коли повертаємося на крок $1$ , то розмір нашого поточного базису $X_{j}$ X_j зменшується хоча б на $1$ .

Кроки $2.1 - 2.2$ 2.1-2.2 можна робити в лоб за $O (m^{2})$ O(m^2):

Повністю перебудуємо XOR базис $X_{j}$ X_j видаливши з нього елемент $v$ за $O (m^{2})$ O(m^2);
Додаємо елементи одного базису $X_{j + 1}$ X_{j+1} в $X_{j} ∖ {v}$ X_j \setminus \{v\} за $O (m^{2})$ O(m^2), щоб знайти $y$ або впевнитися, що такого немає.

Оскільки ці кроки можемо робити в гіршому випадку $m$ разів, то видалення буде працювати за $O (m^{3})$ O(m^3).

Насправді кроки $2.1 - 2.2$ 2.1-2.2 можемо робити за $O (m)$ .

Перед тим як перейти до оптимізації, розглянемо як саме ми представляємо XOR базиси $X_{i}$ X_i, щоб з ними ефективно працювати.

XOR базис

vector <node> basis;
bool add (int x, int id) {
    int mask = 0;
    for (auto &i : basis) {
        if (x > (x ^ i.val)) {
            x ^= i.val;
            mask ^= i.mask;
        } 
    }
    if (x) {
        mask |= 1 << ((int)basis.size());
        for (auto &i : basis) {
            if (i.val > (i.val ^ x)) {
                i.val ^= x;
                i.mask ^= mask;
            }
        }
        basis.push_back(node{val: x, id: id, mask: mask, high: get_high(x)});
        return true;
    }
    return false;
}

C++

Нехай $A$ та $B$ — XOR базиси, що побудовані алгоритмом вище. XOR базис, що представлений у такому вигляді має декілька важливих властивостей та наслідків з неї:

Розглянемо як саме видаляти число $v$ з базису та перебудовувати його за $O (m)$ :

Кожне число базису також має маску $ma s k$ , яка позначає лінійну комбінацію початкових елементів базису, за допомогою яких ми отримали цей елемент базису $v a l$ .
Нам треба зробити так, щоб числа $v$ вже не було у лінійних комбінаціях та при чому базис залишився правильно побудованим (збереглася властивість, яку наводили вище).
Виявляється, що це зробити досить просто. А саме знаходимо таке число базису $x$ , що містить $v$ у лінійній комбінації та серед таких чисел має найменший старший біт.
Далі видаляємо це знайдене число з базису та модифікуємо інші числа базису, що містили $v$ у лінійній комбінації, проXOR-ривши відповідне число з $x$ . Таким чином старший біт у цих числах не зміниться, отже, і властивість збережеться.
Паралельно рахуємо число $bi t s$ , що містить всі старші біти чисел базису, які містили у лінійній комбінації число $v$ .

int rebuild_and_delete (int id) {
    int pos = 0, mn = inf, p2 = 0;
    for (int i = 0; i < basis.size(); i++) {
        if (basis[i].id == id) {
            pos = i;
        }
    }
    int bits = 0;
    for (int i = 0; i < basis.size(); i++) {
        if (basis[i].mask & (1 << pos)) {
            if (mn > basis[i].high) {
                mn = basis[i].high;
                p2 = i;
            }
            bits ^= 1 << basis[i].high;
        }
    }

    if (p2 != pos) {
        swap(basis[p2].id, basis[pos].id);
        for (auto &i : basis) {
            swap_bits(i.mask, pos, p2); // just swaps pos-th and p2-th bit in i.mask
        }
        pos = p2;
    }
    for (int i = 0; i < basis.size(); i++) {
        if (i != pos) {
            if (basis[i].mask & (1 << pos)) {
                basis[i].val ^= basis[pos].val;
                basis[i].mask ^= basis[pos].mask;
            }
        }
    }
    int good = (1 << pos) - 1;
    int other = ((1 << len(basis)) - 1) ^ (good | (1 << pos));
    basis.erase(basis.begin() + pos);
    for (auto &i : basis) {
        i.mask = ((i.mask & other) >> 1) | (i.mask & good);
    }
    return bits;
}

C++

Далі треба знайти $y$ з твердження $1$ за $O (m)$ або сказати, що його не існує. Для $y$ має виконуватись така умова: $span ((X_{j} ∖ {v}) \cup y) = span (X_{j})$ \operatorname{span}((X_j \setminus \{v\}) \cup y)=\operatorname{span}(X_j). Ми знаємо який старший біт зник, при видаленні числа $v$ з $X_{j}$ X_j. Тому при додавання $y \in X_{j + 1}$ y \in X_{j+1} до $X_{j} ∖ {v}$ X_j \setminus \{v\}, $y$ має «відповідати» саме за цей зниклий біт.

Тоді можемо за для кожного $x \in X_{j + 1}$ x \in X_{j+1} за $O (1)$ перевірити чи підходить воно в якості $y$ . Нескладно переконатися, що $x$ підходить тоді та тільки, коли $cnt (bi t s & x) mod 2 = 1$ \operatorname{cnt}(bits \ \& \ x) \ \operatorname{mod} \ 2 = 1, де $cnt (t)$ — функція, що повертає кількість одиничних бітів у числі.

int get_the_same_high_bit (int bits, vector <int> &val) {
    for (auto &i : basis) {
        if (__builtin_popcount(val[i.id] & bits) & 1) {
            return i.id;
        }
    }
    return -1;
}

C++

Тоді ми навчилися видаляти за $O (m^{2})$ O(m^2).

З повною версією кода можна ознайомитись тут:

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;


const int C = 20;

struct node {
    int val, id, mask, high;
};


inline int get_high (int x) {
    if (x == 0) {
        return -1;
    }
    return 31 - __builtin_clz(x);
}

inline void swap_bits (int &x, int a, int b) {
    int x1 = bool(x & (1 << a));
    int x2 = bool(x & (1 << b));
    x ^= (x1 ^ x2) << a;
    x ^= (x1 ^ x2) << b;
}

struct xor_basis {
    vector <node> basis;

    inline bool add (int x, int id) {
        int mask = 0;
        for (auto &i : basis) {
            if (umin(x, x ^ i.val)) {
                mask ^= i.mask;
            }
        }
        if (x) {
            mask |= 1 << len(basis);
            for (auto &i : basis) {
                if (umin(i.val, i.val ^ x)) {
                    i.mask ^= mask;
                }
            }
            basis.pb(node{val: x, id: id, mask: mask, high: get_high(x)});
            return true;
        }
        return false;
    }



    inline int get_the_same_high_bit (int bits, const vector <int> &val) {
        for (auto &i : basis) {
            if (__builtin_popcount(val[i.id] & bits) & 1) {
                return i.id;
            }
        }
        return -1;
    }


    inline int rebuild_and_delete (int id) {
        int pos = 0, mn = inf, p2 = 0;
        for (int i = 0; i < len(basis); i++) {
            if (basis[i].id == id) {
                pos = i;
            }
        }
        int bits = 0;
        for (int i = 0; i < len(basis); i++) {
            if (basis[i].mask & (1 << pos)) {
                if (umin(mn, basis[i].high)) {
                    p2 = i;
                }
                bits ^= 1 << basis[i].high;
            }
        }

        if (p2 != pos) {
            swap(basis[p2].id, basis[pos].id);
            for (auto &i : basis) {
                swap_bits(i.mask, pos, p2);
            }
            pos = p2;
        }
        for (int i = 0; i < len(basis); i++) {
            if (i != pos) {
                if (basis[i].mask & (1 << pos)) {
                    basis[i].val ^= basis[pos].val;
                    basis[i].mask ^= basis[pos].mask;
                }
            }
        }
        int good = (1 << pos) - 1;
        int other = ((1 << len(basis)) - 1) ^ (good | (1 << pos));
        basis.erase(basis.begin() + pos);
        for (auto &i : basis) {
            i.mask = ((i.mask & other) >> 1) | (i.mask & good);
        }
        return bits;
    }

};

template<int max_bit> // not inclusive
struct xor_basis_online {

    vector <xor_basis> basises[max_bit + 1];

    int mx;

    vector <pii> where;
    vector <int> val;

    xor_basis_online() : mx(0), cur_id(0) {}

    int cur_id;

    inline int add (int x) {
        val.pb(x);
        where.pb(make_pair(-1, -1));
        int id = cur_id++;
        if (x == 0) {
            return id;
        }
        for (int i = mx; i >= 0; i--) {
            if (basises[i].empty()) {
                continue;
            }
            if (basises[i].back().add(x, id)) {
                basises[i + 1].pb(basises[i].back());
                basises[i].pop_back();
                umax(mx, i + 1);
                for (auto &j : basises[i + 1].back().basis) {
                    where[j.id] = make_pair(i + 1, len(basises[i + 1]) - 1);
                }
                return id;
            }
        }
        basises[1].pb(xor_basis());
        basises[1].back().add(x, id);
        where.back() = make_pair(1, len(basises[1]) - 1);
        umax(mx, 1);
        return id;
    }

    inline int move_back (int sz, int pos) {
        int to = len(basises[sz]) - 1;
        if (to == pos) {
            return pos;
        }
        for (auto &i : basises[sz][pos].basis) {
            where[i.id].second = to;
        }
        for (auto &i : basises[sz][to].basis) {
            where[i.id].second = pos;
        }
        swap(basises[sz][pos], basises[sz][to]);
        return to;
    }

    inline void del (int id) {
        if (val[id] == 0) {
            return;
        }
        int sz, pos;
        tie(sz, pos) = where[id];
        pos = move_back(sz, pos);
        while (true) {
            int bits = basises[sz].back().rebuild_and_delete(id);
            int i = sz - 1;
            while (i > 0 && basises[i].empty()) {
                --i;
            }
            int new_id = -1;
            if (i > 0) {
                new_id = basises[i].back().get_the_same_high_bit(bits, val);
            }
            if (new_id == -1) {
                if (sz > 1) {
                    basises[sz - 1].pb(basises[sz].back());
                    for (auto &j : basises[sz - 1].back().basis) {
                        where[j.id] = make_pair(sz - 1, len(basises[sz - 1]) - 1);
                    }
                }
                basises[sz].pop_back();
                if (mx > 0 && basises[mx].empty()) {
                    --mx;
                }
                return;
            }
            int cur = val[new_id];
            assert(basises[sz].back().add(cur, new_id));
            int new_sz = i;
            int new_pos = len(basises[i]) - 1;
            where[new_id] = make_pair(sz, pos);
            id = new_id;
            sz = new_sz;
            pos = new_pos;
        }
    }

    inline int size () {
        return mx;
    }
};

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);


    // solution to https://basecamp.eolymp.com/uk/problems/11732
    int n, q, add;
    cin >> n >> add;
    vector <int> p(n);
    xor_basis_online<19> t;
    vector <int> now(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        now[i] = t.add(i ^ p[i]);
    }
    cin >> q;
    int ans = t.size();
    cout << ans << '\n';
    for (int i = 0, l, r; i < q; i++) {
        cin >> l >> r;
        l = (l + ans * add) % n;
        r = (r + ans * add) % n;
        if (l != r) {
            t.del(now[l]);
            t.del(now[r]);
            swap(p[l], p[r]);
            now[l] = t.add(l ^ p[l]);
            now[r] = t.add(r ^ p[r]);
        }
        ans = t.size();
        cout << ans << '\n';
    }
}

C++

P. S. Подібно до додавання, ми можемо спробувати використати бінарний пошук для видалення: знайти максимальне $r$ , що $span (X_{j} ∖ {v}) ⊉ span (X_{r})$ \operatorname{span}(X_j \setminus \{v \}) \nsupseteq \operatorname{span}(X_r). Але після переміщення цілого числа від $X_{r}$ X_r до $X_{j}$ X_j властивість послідовності базисів все ще може не виконуватися. І тому використання бінарного пошуку не покращує часову складність.

Деякий час я думав, що ми можемо зробити краще, ніж $O (m^{2})$ O(m^2), але не вдалося покращити. Справа в тому, що за допомогою цієї властивості $span (X_{i}) \supseteq span (X_{i + 1})$ \operatorname{span}(X_i) \supseteq \operatorname{span}(X_{i+1}) ми можемо побудувати послідовність цілих чисел $a_{i}$ a_i так, що $span (X_{i}) = span ({a_{1}, a_{2}, \dots, a_{d i m (X_{i})}})$ \operatorname{ span}(X_i)=\operatorname{span}(\{a_1, a_2, \ldots, a_{\dim(X_i)} \}) для всіх $i$ . Маючи її, ми фактично можемо додавати за $O (m)$ , але все ще не можу зрозуміти, як оптимізувати видалення.

XOR базис з видаленнями

Передмова

Вступ

Структура

Додавання числа v до S

Видалення числа v∈Sv \in S

Коментарі2

Додавання числа $v$ до $S$

Видалення числа $v \in S$ v \in S