ET OU XOR#11862

ET OU XOR (Corrigé)

Auteur du problème:	TheSensei
Préparé par:	Hasan Saleh (MathModel)
Édité par:	Hasan Saleh (MathModel)

Énoncé du problème

Étant donné un tableau $a$ de longueur $n$ , divisez-le en trois segments contigus non vides :

Segment 1: $a_{1}, a_{2}, \dots, a_{i}$ a_1, a_2, \dots, a_i
Segment 2: $a_{i + 1}, a_{i + 2}, \dots, a_{j}$ a_{i+1}, a_{i+2}, \dots, a_j
Segment 3: $a_{j + 1}, a_{j + 2}, \dots, a_{n}$ a_{j+1}, a_{j+2}, \dots, a_n

Trouvez des indices $i < j$ i<j et un entier $x$ tel que

(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.

Si une telle division existe, imprimez un $(i, j, x)$ (i,j,x) valide ; sinon, imprimez $- 1$ .

L'idée principale est de remarquer que le Bitwise-OR d'un segment d'entiers positifs est croissant. C'est une propriété vraie, avec ce fait, nous pouvons pré-calculer le prefix-AND que nous appellerons $p$ et le suffix-XOR que nous appellerons $s$ . Nous pouvons itérer à travers le $i_{e ˋ m e}$ i_{ème} préfixe de Bitwise AND et effectuer une recherche binaire pour le premier $j > i$ j>i tel que

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

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

. Une fois que nous avons trouvé un tel index $j$ , nous vérifions si $s_{n - 1 - j}$ s_{n-1-j} correspond également ; si c'est le cas, nous imprimons $(i, j, p_{i})$ (i,j,p_i) sinon nous continuons à chercher jusqu'à ce que nous ayons exploré toutes les options.

Le Bitwise OR de certains sous-tableaux peut être pré-calculé efficacement en utilisant un Segment Tree ou un Sparse Table. L'implémentation suivante utilise un Segment Tree.

Complexité $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++