Видалення OR від Нассера#12433

Видалення OR від Нассера (Розбір)

Автор задачі:	Mohammad Nasser (MOAGEZA)
Підготував:	Mohammad Nasser (MOAGEZA)
Редактор:	Hasan Saleh (MathModel)

Розв'язання

Загальна ідея:

Елемент $a_{i}$ a_i є несумісним з $k$ , якщо в ньому встановлено біт, якого немає в $k$ — формально, якщо $(a_{i} & \sim k) \neq = 0$ (a_i \,\&\, \sim k) \neq 0, тобто $a_{i}$ a_i має принаймні один біт, який дорівнює $1$ в $a_{i}$ a_i, але $0$ в $k$ . Такий елемент ніколи не може бути частиною підмасиву, OR якого дорівнює $k$ , тому його потрібно видалити. Замінімо кожен несумісний елемент на $0$ і запишемо його позицію в масив префіксних сум $sum$ , щоб $sum [r] - sum [l - 1]$ \mathit{sum}[r] - \mathit{sum}[l-1] давало кількість видалень, потрібних на відрізку $[l, r]$ [l, r].

Після занулення несумісних елементів побудуємо sparse table на зміненому масиві, щоб відповідати на запити OR на відрізку за $O (1)$ .

Крок 1 — Мінімальна кількість видалень:

Для кожної лівої межі $i$ виконаємо бінарний пошук найменшої правої межі $r$ , такої що $OR (i, r) = k$ \mathrm{OR}(i, r) = k. Вартість вікна $[i, r]$ дорівнює $sum [r] - sum [i - 1]$ \mathit{sum}[r] - \mathit{sum}[i-1]. Візьмемо мінімум за всіма коректними вікнами:

ans = i min (sum [r^{*}] - sum [i - 1])

\mathit{ans} = \min_{i} \bigl(\mathit{sum}[r^*] - \mathit{sum}[i-1]\bigr)

Якщо жодне вікно ніколи не досягає OR $= k$ , виводимо -1 -1.

Крок 2 — Максимальна довжина:

Для кожної лівої межі $i$ виконаємо бінарний пошук найбільшої правої межі $r$ , такої що кількість видалень на $[i, r]$ не перевищує $ans$ і $OR (i, r) = k$ \mathrm{OR}(i, r) = k. Ефективна довжина отриманого підмасиву (після видалень) дорівнює $(r - i + 1) - ans$ (r - i + 1) - \mathit{ans}. Візьмемо максимум за всіма коректними вікнами:

len = i max ((r - i + 1) - ans)

\mathit{len} = \max_{i} \bigl((r - i + 1) - \mathit{ans}\bigr)

Розв'язок працює за $O (n lo g n + \sum n)$ \mathcal{O}\!\left(n \log n + \sum n\right) часу на один вхідний файл, де доданок $n lo g n$ n \log n виникає через побудову sparse table і два проходи бінарного пошуку.

#include <bits/stdc++.h>
#define ll long long
#define rv return void
#define vec vector
#define Moageza ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

const int N = 2e5 + 5;
int n, k, a[N], T[N][22], Log[N];

int merge(int a, int b) { return (a | b); }

void build() {
    for (int i = 1; i <= n; i++) T[i][0] = a[i];
    for (int pw = 1; (1 << pw) <= n; pw++)
        for (int i = 1; i + (1 << pw) - 1 <= n; i++)
            T[i][pw] = merge(T[i][pw-1], T[i+(1<<(pw-1))][pw-1]);
}

int query(int l, int r) {
    int pw = Log[r - l + 1];
    return merge(T[l][pw], T[r-(1<<pw)+1][pw]);
}

void preCount() {
    Log[1] = 0;
    for (int i = 2; i < N; i++) Log[i] = Log[i >> 1] + 1;
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    vec<int> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        bitset<30> f = a[i], s = k;
        bool bad = false;
        for (int j = 0; j < 30; j++)
            if (f[j] && !s[j]) bad = true;
        if (bad) { a[i] = 0; sum[i] = 1; }
    }
    for (int i = 1; i <= n; i++) sum[i] += sum[i-1];

    build();

    int ans = 1e9, len = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (query(i, mid) == k) {
                ans = min(ans, sum[mid] - sum[i-1]);
                r = mid - 1;
            } else l = mid + 1;
        }
    }

    if (ans == (int)1e9) rv(cout << "-1 -1");

    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (sum[mid] - sum[i-1] <= ans) {
                l = mid + 1;
                if (query(i, mid) == k)
                    len = max(len, (mid - i + 1) - ans);
            } else r = mid - 1;
        }
    }
    cout << ans << " " << len;
}

signed main() {
    Moageza
    preCount();
    int t; cin >> t;
    while (t--) { solve(); cout << "\n"; }
    return 0;
}