AND OR XOR#11862

AND OR XOR (Розбір)

Автор проблеми:	TheSensei
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Умова задачі

Дано масив $a$ довжини $n$ , розділіть його на три непорожні суміжні сегменти:

Сегмент 1: $a_{1}, a_{2}, \dots, a_{i}$ a_1, a_2, \dots, a_i
Сегмент 2: $a_{i + 1}, a_{i + 2}, \dots, a_{j}$ a_{i+1}, a_{i+2}, \dots, a_j
Сегмент 3: $a_{j + 1}, a_{j + 2}, \dots, a_{n}$ a_{j+1}, a_{j+2}, \dots, a_n

Знайдіть індекси $i < j$ i<j та ціле число $x$ таке, що

(a_{1} & a_{2} & \dots & a_{i}) = (a_{i + 1} ∣ a_{i + 2} ∣ \dots ∣ a_{j}) = (a_{j + 1} \oplus a_{j + 2} \oplus \dots \oplus a_{n}) = x .

(a_1 \mathbin{\&} a_2 \mathbin{\&} \dots \mathbin{\&} a_i) = (a_{i+1} \mathbin{|} a_{i+2} \mathbin{|} \dots \mathbin{|} a_j) = (a_{j+1} \mathbin{\oplus} a_{j+2} \mathbin{\oplus} \dots \mathbin{\oplus} a_n) = x.

Якщо таке розділення існує, виведіть один дійсний $(i, j, x)$ (i,j,x); в іншому випадку виведіть $- 1$ .

Основна ідея полягає в тому, щоб помітити, що побітове OR сегмента додатних цілих чисел є зростаючим. Це справжня властивість, з цим фактом ми можемо попередньо обчислити префікс-AND, нехай це буде $p$ , і суфікс-XOR, нехай це буде $s$ . Ми можемо ітерувати через $i_{й}$ i_{й} префікс побітового AND і виконати бінарний пошук для першого $j > i$ j>i так, що

a_{i + 1} OR a_{i + 2} OR ... OR a_{j} = p_{i}

a_{i+1} \text{ OR } a_{i+2} \text{ OR } ... \text{ OR} a_j = p_i

. Як тільки ми знайшли такий індекс $j$ , ми перевіряємо, чи також збігається $s_{n - 1 - j}$ s_{n-1-j}; якщо так, то ми виводимо $(i, j, p_{i})$ (i,j,p_i), інакше продовжуємо шукати, поки не дослідимо всі варіанти.

Побітове OR деякого підмасиву можна ефективно попередньо обчислити, використовуючи Дерево Сегментів або Розріджену Таблицю. Наступна реалізація використовує Дерево Сегментів.

Складність $O (n lo g^{2} n)$ \mathcal{O}(n\log^2n)

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> t;
void build(int v,int l,int r,vector<int>&a){
    if(l==r) t[v]=a[l];
    else{
        int m=(l+r)/2;
        build(v*2,l,m,a);
        build(v*2+1,m+1,r,a);
        t[v]=t[v*2]|t[v*2+1];
    }
}
int query(int v,int l,int r,int ql,int qr){
    if(ql>r||qr<l) return 0;
    if(ql<=l&&r<=qr) return t[v];
    int m=(l+r)/2;
    return query(v*2,l,m,ql,qr)|query(v*2+1,m+1,r,ql,qr);
}

void solve(){
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<int>p(n);
    p[0]=a[0];
    for(int i=1;i<n;i++)p[i]=p[i-1]&a[i];
    vector<int>s(n);
    s[0]=a[n-1];
    for(int k=1;k<n;k++)s[k]=s[k-1]^a[n-1-k];
    t.assign(4*n,0);
    build(1,0,n-1,a);
    for(int i=0;i<n-2;i++){
        int cur=p[i];
        int l=i+1,r=n-2,j1=-1;
        while(l<=r){
            int mid=(l+r)/2;
            int val=query(1,0,n-1,i+1,mid);
            if(val<cur) l=mid+1;
            else{
                if(val==cur) j1=mid;
                r=mid-1;
            }
        }
        if(j1==-1) continue;
        l=j1; r=n-2;
        int j2=n-1;
        while(l<=r){
            int mid=(l+r)/2;
            int val=query(1,0,n-1,i+1,mid);
            if(val>cur){j2=mid;r=mid-1;}
            else l=mid+1;
        }
        for(int j=j1;j<j2;j++){
            if(s[n-2-j]==cur){
                cout<<i+1<<" "<<j+1<<" "<<cur<<"\n";
                return;
            }
        }
    }
    cout<<"-1\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}

C++