1665E - MinimizOR - CodeForces Solution

#include<bits/stdc++.h>
using namespace std ; 
#define maxn 100009 
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1
#define re exit(0); 
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
#define EXP 1e-6

#define YES "YES" 
#define NO "NO" 
#define Yes "Yes" 
#define No "No" 

const int mod = 1e9+7 ; 
const int LOG = 19 ; 
const int INF = 2e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ; 
typedef vector<ll> vl ;
 
void add ( int &a , int b ){ if ((a+=b)>=mod) a -= mod;};
void sub ( int &a , int b ){ if ((a-=b)<0) a += mod;};  

template < typename T > void chkmin ( T&a , T b ) { if ( a > b ) a = b ; } ; 
template < typename T > void chkmax ( T&a , T b ) { if ( a < b ) a = b ; } ; 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return (1ll*res*res%mod*a%mod) ; 
	else return (1ll*res*res%mod) ; 
}

int n , nq ; 
int a [maxn] ; 

pii T [maxn*4] ; 
void update ( int id , int l , int r , int pos , int val ) 
{
	if ( l > pos || r < pos ) return ; 
	if ( l == r ) 
	{
		T [id] = {val,pos} ; 
		return ; 
	}
	int mid = (l+r)/2 ; 
	update (left,l,mid,pos,val) ; 
	update (right,mid+1,r,pos,val) ; 
	T [id] = min (T[left],T[right]) ; 
}

pii get ( int id , int l , int r , int u , int v ) 
{
	if ( l > v || r < u ) return {INF,INF} ; 
	if ( u <= l && r <= v ) return T [id] ; 
	int mid = (l+r)/2 ; 
	return min (get(left,l,mid,u,v),get(right,mid+1,r,u,v)) ; 
}

int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0);cout.tie(0) ; 
//	rf () ; 
	int test ; cin >> test ; 
	while ( test -- ) 
	{
		cin >> n ;
		for ( int i = 1 ; i <= n*4 ; i ++ ) T [i] = {INF,INF} ;
		for ( int i = 1 ; i <= n ; i ++ ) 
		{
			cin >> a [i] ; 
			update (1,1,n,i,a[i]) ;
		}
		cin >> nq ; 
		while ( nq -- ) 
		{
			int l , r ; cin >> l >> r ; 
			int TIME = min (r-l+1,31) ; 
			vi vec ; 
			while ( TIME -- ) 
			{
				pii Min = get(1,1,n,l,r) ;
				vec . pb (Min.se) ;  
				update (1,1,n,Min.se,INF) ; 
			}
			
			int res = INF ; 
			for ( int i = 0 ; i < vec.size () ; i ++ ) 
			{
				for ( int j = i+1 ; j < vec.size () ; j ++ ) 
				{
					chkmin (res,a[vec[i]]|a[vec[j]]) ; 
				}
			}
			
			cout << res << "\n" ; 
			
			for ( auto x : vec ) update (1,1,n,x,a[x]) ; 
		}
	}
}

// std=c++11 thunopro