Побітова вечірка#12463

Побітова вечірка (Розбір)

Автор задачі:	Hadi Takla (TaklaOI)
Підготував:	Hadi Takla (TaklaOI)
Відредагував:	Hadi Takla (TaklaOI)

Розв'язок

Спочатку спростимо задану операцію.

Коли ми беремо відрізок $l, r$ , спочатку ми встановлюємо $x = a_{l} & a_{l + 1} &...& a_{r}$ x = a_l \& a_{l+1} \& ... \& a_r, що означає, що $x$ містить лише спільні біти на відрізку $(l, r)$ (l,r), тому коли ми замінюємо кожен елемент $a_{i}$ a_i на відрізку $l, r$ на $a_{i} \oplus x$ a_i \oplus x, ми вимикаємо спільні біти на цьому відрізку.

Тепер нам потрібно мінімізувати побітове або масиву.

Припустимо, нам потрібно вимкнути біт $x$ в результаті або, це означає, що ми повинні вимкнути всі входження біта $x$ в масиві $a$ .

Нехай $f r [i]$ — перший індекс, де біт $i$ увімкнено, $l s t [i]$ — останній індекс, де біт $i$ увімкнено.

Ми можемо вимкнути біт $i$ у фінальній відповіді тоді і тільки тоді, коли біт $i$ є спільним на відрізку ( $f r [i], l s t [i]$ fr[i] , lst[i]). Чому?

Оскільки $f r [i]$ — перший індекс, де біт $i$ увімкнено, а $l s t [i]$ — останній індекс, де біт $i$ увімкнено, то будь-який відрізок ( $l, r$ ), де $l < f r [i]$ l < fr[i] або $r > l s t [i]$ r > lst[i], не матиме біт $i$ як спільний біт.

І будь-який відрізок $(l, r)$ (l , r), де $l > f r [i]$ l > fr[i] або $r < l s t [i]$ r < lst[i], не вплине на значення фінальної відповіді.

Тому єдиним відрізком-кандидатом є $f r [i], l s t [i]$ fr[i] , lst[i].

Ми можемо перебрати всі $30$ бітів і для кожного біта спробувати застосувати операцію на $f r [i], l s t [i]$ fr[i] , lst[i], а потім взяти мінімальну відповідь.

Часова складність: $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;
    }
}