Bitwise Party#12463

Bitwise Party (Editorial)

Problem Author:	Hadi Takla (TaklaOI)
Prepared by:	Hadi Takla (TaklaOI)
Edited by:	Hadi Takla (TaklaOI)

Solution

First , let's simplify the given operation.

when we take a range $l, r$ , first we set $x = a_{l} & a_{l + 1} &...& a_{r}$ x = a_l \& a_{l+1} \& ... \& a_r , which means that $x$ contains only common bits in the range $(l, r)$ (l,r) , so when we replace each element $a_{i}$ a_i in the range $l, r$ by $a_{i} \oplus x$ a_i \oplus x , we are turning off the common bits in the range.

now we need to minimize the bitwise or of the array.

suppose we need to turn off a bit $x$ in the or , it means that we should turn off all occurrences of the bit $x$ in the array $a$ .

now , let $f r [i]$ be the first index where the bit $i$ is turned on , $l s t [i]$ is the last index where the bit $i$ is turned on.

we can turn the bit $i$ off in the final answer if and only if the bit $i$ is common in range ( $f r [i], l s t [i]$ fr[i] , lst[i]), why ?

since $f r [i]$ is the first index where the bit $i$ is turned on , and $l s t [i]$ is the last index where the bit $i$ is turned on , so any range ( $l, r$ ) where $l < f r [i]$ l < fr[i] or $r > l s t [i]$ r > lst[i] won't has the bit $i$ as a common bit.

and any range $(l, r)$ (l , r) where $l > f r [i]$ l > fr[i] or $r < l s t [i]$ r < lst[i] won't affect the final answer value.

so the only candidate range is $f r [i], l s t [i]$ fr[i] , lst[i].

we can iterate over all $30$ bits , and for each bit try to apply the operation on $f r [i], l s t [i]$ fr[i] , lst[i] , then take the minimum answer.

Time complexity : $O (30 \cdot n)$ \mathcal{O}(30 \cdot n).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        int a[n+1] , ans = 0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            ans |= a[i];
        }
        int fr[32]={0},lst[32]={0};
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=30;j++)
            {
                if(a[i] & (1LL<<j))
                lst[j] = i;
            }
        }
        for(int i=n;i>=1;i--)
        {
            for(int j=0;j<=30;j++)
            {
                if(a[i] & (1LL<<j))
                fr[j] = i;
            }
        }
        for(int j=0;j<=30;j++)
        {
            int x = (1LL<<31)-1;
            for(int i=fr[j];i<=lst[j];i++)
            x &= a[i];
            for(int i=fr[j];i<=lst[j];i++)
            a[i] ^= x;
            int cur = 0;
            for(int i=1;i<=n;i++)
            cur |= a[i];
            for(int i=fr[j];i<=lst[j];i++)
            a[i] ^= x;
            ans = min(ans , cur);
        }
        cout<<ans<<endl;
    }
}