AND OR XOR#11862

AND OR XOR (Həll təhlili)

Problem Müəllifi:	TheSensei
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Problem Təsviri

Uzunluğu $n$ olan $a$ massivini üç boş olmayan ardıcıl seqmentə bölün:

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

İndeks $i < j$ i<j və bir tam ədəd $x$ tapın ki,

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

Belə bir bölmə varsa, bir etibarlı $(i, j, x)$ (i,j,x) çap edin; əks halda, $- 1$ çap edin.

Əsas fikir, müsbət ədədlərin seqmentinin Bitwise-OR-unun artan olduğunu başa düşməkdir. Bu, doğru bir xüsusiyyətdir, bu faktla biz prefix-AND-i əvvəlcədən hesablaya bilərik, onu $p$ adlandıraq və suffix-XOR-u $s$ adlandıraq. Biz Bitwise AND-in $i_{t h}$ i_{th} prefix-i boyunca iterasiya edə bilərik və ilk $j > i$ j>i üçün ikili axtarış edirik ki,

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

. Belə bir indeks $j$ tapdıqda, $s_{n - 1 - j}$ s_{n-1-j}-nin də uyğun olub olmadığını yoxlayırıq, əgər uyğun gəlirsə, $(i, j, p_{i})$ (i,j,p_i) çap edirik, əks halda bütün variantları araşdırana qədər axtarışa davam edirik.

Bəzi alt massivlərin Bitwise OR-u Segment Tree və ya Sparse Table istifadə edərək effektiv şəkildə əvvəlcədən hesablana bilər. Aşağıdakı İcra Segment Tree istifadə edir.

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