自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:16:32，当前版本为作者最后更新于2025-05-25 08:28:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

哎这个真的很套路吗。

首先考虑 $l=1$ 且 $r=n$ 咋做。这种二进制问题，考虑按位贪。建出一个 01 trie 树，考虑依次决策每一位。

当 trie 树这一位只有 $1$ 个儿子的时候，我们可以控制答案这一位是 $1$；否则，我们要在两个子树中选一个出来作为这一位是 $0$，那么显然选的是较大值。

也就是说，我们是这样一个树形 DP：设 $dp_{u}$ 表示考虑 $u$ 的子树中能得到的最大答案。则

或

直接莫队的话，似乎可以做到 $O(nm \sqrt q)$，应该过不去。

将所有的 $\max$ 拆开，等价于：选一个根到叶子的路径。如果路径上一点没有邻居，那么会带来 $2^d$ 的贡献。

发现我们可以维护出这个数每一位，左边和右边第一个邻居的位置 $l_d$ 和 $r_d$。这样如果询问的 $l$ 和 $r$ 满足 $l_d < l \le r < r_d$ 那么就可以带来 $2^d$ 的贡献。

所以对于每个位置来说，他只有 $O(m^2)$ 个本质不同的区间。然后查询相当于一个二维数点问题，所以你可以做到 $O(q \log n + n m^2 \log n)$。

但是这样有点魔怔了，因为你发现查询本质上是 2-side 矩形，而且 $nm^2$ 远大于 $q$。所以考虑使用值域分块来平衡一下复杂度，做到 $O(q \sqrt n + nm^2)$，足以通过本题。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,B=320;
int n,m,q,l[MAXN][55],r[MAXN][55];
ll a[MAXN];
vector<pair<int,ll>> u1[MAXN],u2[MAXN]; 
namespace ZYFK {
	int L[MAXN],R[MAXN],bel[MAXN];
	ll mx1[MAXN],mx2[MAXN];
	void init(void) {
		int k=(n+B-1)/B;
		ffor(i,1,k) L[i]=R[i-1]+1,R[i]=min(n,i*B);
		ffor(i,1,k) ffor(j,L[i],R[i]) bel[j]=i;
		return ;
	}
	void update(int pos,ll v) {
		mx1[pos]=max(mx1[pos],v),mx2[bel[pos]]=max(mx2[bel[pos]],v);
		return ;	
	}
	ll query(int pos) {
		ll ans=0;
		ffor(i,1,bel[pos]-1) ans=max(ans,mx2[i]);
		ffor(i,L[bel[pos]],pos) ans=max(ans,mx1[i]);
		return ans;	
	}
};
vector<pair<int,int>> qr[MAXN];
ll ans[MAXN*5];

int tot=1,tr[MAXN*50][2],vis[MAXN*50];
void insert(ll v) {
	int u=1;
	roff(i,m-1,0) {
		int op=!!(v&(1ll<<i));
		if(!tr[u][op]) tr[u][op]=++tot;
		u=tr[u][op];
	}
	return ;
}
void mark(ll v,int id) {
	int u=1;
	roff(i,m-1,0) {
		int op=!!(v&(1ll<<i));
		vis[u]=id,u=tr[u][op];	
	}
	vis[u]=id;
	return ;
}
void solve1(ll v,int id) {
	int u=1;
	roff(i,m-1,0) {
		int op=!!(v&(1ll<<i));
		if(!tr[u][op^1]||vis[tr[u][op^1]]==0) l[id][i]=0;
		else l[id][i]=vis[tr[u][op^1]];
		u=tr[u][op];
	}
	return ;
}
void solve2(ll v,int id) {
	int u=1;
	roff(i,m-1,0) {
		int op=!!(v&(1ll<<i));
		if(!tr[u][op^1]||vis[tr[u][op^1]]==0) r[id][i]=n+1;
		else r[id][i]=vis[tr[u][op^1]];
		u=tr[u][op];
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q>>m;
	ffor(i,1,n) cin>>a[i];
	ffor(i,1,n) insert(a[i]);
	ffor(i,1,n) solve1(a[i],i),mark(a[i],i);
	memset(vis,0,sizeof(vis));
	roff(i,n,1) solve2(a[i],i),mark(a[i],i);
	ffor(i,1,n) {
		vector<pair<int,int>> vl;
		ffor(j,0,m-1) vl.push_back({l[i][j],j});
		sort(vl.begin(),vl.end(),[](pair<int,int> A,pair<int,int> B) {
			return A>B;
		});
		int pos=0;
		ll ov=0;
		while(pos<vl.size()) {
			int id=vl[pos].first;
			if(id==0) break ;
			u1[i].push_back({id,ov});
			while(pos<vl.size()&&vl[pos].first==id) ov|=(1ll<<vl[pos].second),pos++;
		}
		u1[i].push_back({0,ov});
		pos=0,ov=0,vl.clear();
		ffor(j,0,m-1) vl.push_back({r[i][j],j});
		sort(vl.begin(),vl.end());
		while(pos<vl.size()) {
			int id=vl[pos].first;
			if(id==n+1) break ;
			u2[id-1].push_back({i,ov});
			while(pos<vl.size()&&vl[pos].first==id) ov|=(1ll<<vl[pos].second),pos++;
		}
		u2[n].push_back({i,ov});
	}
	ZYFK::init();
	ffor(i,1,q) {
		int l,r;
		cin>>l>>r,qr[r].push_back({l,i});	
	}
	roff(i,n,1) {
		for(auto pr:u2[i]) {
			int id=pr.first;
			ll Ov=pr.second;
			for(auto ppr:u1[id]) {
				int ul=ppr.first;
				ll ov=Ov;
				ov|=ppr.second,ov^=(1ll<<m)-1;
				ZYFK::update(ul+1,ov);	
			}
		}
		for(auto pr:qr[i]) ans[pr.second]=ZYFK::query(pr.first);
	}
	ffor(i,1,q) cout<<ans[i]<<'\n';
	return 0;
}