AND OR XOR#11862

AND OR XOR (Editorial)

Problem Author:	TheSensei
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Problem Statement

Given an array $a$ of length $n$ , split it into three non-empty contiguous segments:

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

Find indices $i < j$ i<j and an integer $x$ such that

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

If such a split exists, print one valid $(i, j, x)$ (i,j,x); otherwise, print $- 1$ .

The main idea is noticing that Bitwise-OR of segment of positive integers is increasing , This is a true property , with this fact we can precompute the prefix-AND let it be $p$ and suffix-XOR let it be $s$ , we can iterate through the $i_{t h}$ i_{th} prefix of Bitwise AND and we binary search for the first $j > i$ j>i such

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

, Once we found such index $j$ then we check if $s_{n - 1 - j}$ s_{n-1-j} matches as well , if so then we print $(i, j, p_{i})$ (i,j,p_i) otherwise we keep looking until we've explored all options.

The Bitwise OR of some subarray can be precalculated efficiently using Segment Tree or Sprase Table , The following Implementation uses Segment Tree.

Complexity $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++