魔法序列 题解

给定一个序列 $a$，$q$ 次询问，每次询问给定一段区间 $[l,r]$ 和一个数 $x$，求

\[\max_{l\le i\le r}a_i\vee x\]

其中 $\vee$ 表示二进制按位或。

咕

#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=1<<20|1;
int n,m,a[N],sz[N<<2],dep[N];
vector<int>f[N<<2],g;
#define ls (u<<1)
#define rs (u<<1|1)
void build(int u,vector<int>b,int d){
	f[u].resize(1<<d);
	dep[u]=d;
	if(d==0){
		if(!b.empty())f[u][0]=b[0];
		return;
	}
	vector<int>b1,b2;
	for(int i:b)
		((i>>(d-1)&1)?b2:b1).push_back(i);
	build(ls,b1,d-1);
	build(rs,b2,d-1);
	int U=(1<<(d-1))-1;
	for(int i=0;i<(1<<d);i++){
		int x=f[ls][i&U],y=f[rs][i&U];
		f[u][i]=(x|i)>(y|i)?x:y;
	}
}
#define mid ((l+r)>>1)
int ask(int u,int l,int r,int x,int y,int k){
	if(x<=l&&r<=y)return k|f[u][k&((1<<dep[u])-1)];
	int res=0;
	if(x<=mid)res=max(res,ask(ls,l,mid,x,y,k));
	if(y>mid)res=max(res,ask(rs,mid+1,r,x,y,k));
	return res;
}
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],g.push_back(a[i]);
	build(1,g,20);
	cin>>m;
	for(int l,r,x;m--;){
		cin>>l>>r>>x;
		cout<<ask(1,0,N-2,a[l],a[r],x)<<'\n';
	}
	return 0;
}