•Статті•1 рік тому

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

Передмова

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

Ціле число між $0$ (включно) і $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}$ ( $xor$ порожньої множини дорівнює $0$ ).

Вступ

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

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

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

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

Структура

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Нехай $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;
}

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

Тоді можемо за для кожного $x \in X_{j + 1}$ за $O (1)$ перевірити чи підходить воно в якості $y$ . Нескладно переконатися, що $x$ підходить тоді та тільки, коли $cnt (bi t s & x) 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;
}

Тоді ми навчилися видаляти за $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';
    }
}

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

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

Коментарі (2)

user429879•2 місяці тому

👍🏻

SANYAAAAAAAAAAAAA•7 місяців тому•2-а ревізія

Is it possible to get size of set of integers that belong to a span of at least one basis, several basises given

Завантаження

Секундочку, отримую дані з серверу

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

Передмова

Вступ

Структура

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

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

Завантаження

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

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