Nasser's OR Removal#12433

Nasser's OR Removal (Editorial)

Problem Author:	Mohammad Nasser (MOAGEZA)
Prepared by:	Mohammad Nasser (MOAGEZA)
Edited by:	Hasan Saleh (MathModel)

Solution

General Idea:

An element $a_{i}$ a_i is incompatible with $k$ if it has a bit set that $k$ does not — formally, if $(a_{i} & \sim k) \neq = 0$ (a_i \,\&\, \sim k) \neq 0, i.e. $a_{i}$ a_i has at least one bit that is $1$ in $a_{i}$ a_i but $0$ in $k$ . Such an element can never be part of a subarray whose OR equals $k$ , so it must be removed. Replace every incompatible element with $0$ and record its position in a prefix sum array $sum$ , so that $sum [r] - sum [l - 1]$ \mathit{sum}[r] - \mathit{sum}[l-1] gives the number of removals needed in the range $[l, r]$ [l, r].

After zeroing incompatible elements, build a sparse table on the modified array to answer range OR queries in $O (1)$ .

Step 1 — Minimum removals:

For each left endpoint $i$ , binary search for the smallest right endpoint $r$ such that $OR (i, r) = k$ \mathrm{OR}(i, r) = k. The cost of the window $[i, r]$ is $sum [r] - sum [i - 1]$ \mathit{sum}[r] - \mathit{sum}[i-1]. Take the minimum over all valid windows:

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

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

If no window ever achieves OR $= k$ , output -1 -1.

Step 2 — Maximum length:

For each left endpoint $i$ , binary search for the largest right endpoint $r$ such that the number of removals in $[i, r]$ does not exceed $ans$ and $OR (i, r) = k$ \mathrm{OR}(i, r) = k. The effective length of the resulting subarray (after removals) is $(r - i + 1) - ans$ (r - i + 1) - \mathit{ans}. Take the maximum over all valid windows:

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

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

The solution runs in $O (n lo g n + \sum n)$ \mathcal{O}\!\left(n \log n + \sum n\right) time per test file, where the $n lo g n$ n \log n term comes from the sparse table construction and the two binary search passes.

#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;
}