Nasserin OR Silinməsi#12433

Nasserin OR Silinməsi (Həll təhlili)

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

Həll

Ümumi ideya:

Əgər $a_{i}$ a_i elementində $k$ -da olmayan hər hansı bir bit $1$ -dirsə, onda $a_{i}$ a_i elementi $k$ ilə uyğunsuz sayılır — formal olaraq, əgər $(a_{i} & \sim k) \neq = 0$ (a_i \,\&\, \sim k) \neq 0 olarsa, yəni $a_{i}$ a_i-də elə ən azı bir bit var ki, $a_{i}$ a_i-də $1$ , amma $k$ -da $0$ -dır. Belə element heç vaxt OR-u $k$ -ya bərabər olan bir altmassivin hissəsi ola bilməz, buna görə də o silinməlidir. Hər bir uyğunsuz elementi $0$ ilə əvəz edin və onun mövqeyini prefiks cəmi massivi $sum$ -da qeyd edin ki, $sum [r] - sum [l - 1]$ \mathit{sum}[r] - \mathit{sum}[l-1] ifadəsi $[l, r]$ [l, r] aralığında lazım olan silinmələrin sayını versin.

Uyğunsuz elementləri sıfırladıqdan sonra dəyişdirilmiş massiv üzərində aralıq OR sorğularını $O (1)$ vaxtda cavablandırmaq üçün sparse table qurun.

Addım 1 — Minimum silinmələr:

Hər bir sol sərhəd $i$ üçün elə ən kiçik sağ sərhəd $r$ -i ikili axtarışla tapın ki, $OR (i, r) = k$ \mathrm{OR}(i, r) = k olsun. $[i, r]$ pəncərəsinin dəyəri $sum [r] - sum [i - 1]$ \mathit{sum}[r] - \mathit{sum}[i-1] olacaq. Bütün uyğun pəncərələr üzrə minimumu götürün:

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

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

Əgər heç bir pəncərə OR $= k$ əldə etmirsə, -1 -1 çıxış verin.

Addım 2 — Maksimum uzunluq:

Hər bir sol sərhəd $i$ üçün elə ən böyük sağ sərhəd $r$ -i ikili axtarışla tapın ki, $[i, r]$ aralığındakı silinmələrin sayı $ans$ -ı aşmasın və $OR (i, r) = k$ \mathrm{OR}(i, r) = k olsun. Alınan altmassivin effektiv uzunluğu (silinmələrdən sonra) $(r - i + 1) - ans$ (r - i + 1) - \mathit{ans} olacaq. Bütün uyğun pəncərələr üzrə maksimumu götürün:

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

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

Həllin işləmə vaxtı hər test faylı üçün $O (n lo g n + \sum n)$ \mathcal{O}\!\left(n \log n + \sum n\right)-dir; burada $n lo g n$ n \log n hissəsi sparse table qurulmasından, qalan hissə isə iki ikili axtarış keçidindən gəlir.

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