自动搬运

查看原文

来自洛谷，原作者为

	IdnadRev 你要把眼泪汇编成册

搬运于2025-08-24 22:50:54，当前版本为作者最后更新于2023-10-04 11:17:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先，如果 swap，那么 $k$ 一定在 swap 的一对位置中间。

不妨提取出改变前缀 $\operatorname{and}$ 值与后缀 $\operatorname{and}$ 值的 $\log$ 个关键点。

如果交换非两个关键点，对应的前缀/后缀权值不会变大，因此不优。

如果交换一个关键点，一个非关键点。不妨假设是枚举的前缀关键点 $i$ 与非关键点 $j$，那么每个 $k$ 对应权值应是（记 $f(i,j)$ 为 $[i,j]$ 区间 $\operatorname{and}$ 值）：

$$(f(1,i-1)\operatorname{and} f(i+1,k)\operatorname{and} a_j)+(f(k+1,n)\operatorname{and}a_i) $$

枚举 $i$ 后右边的值固定，而左边注意到 $f(1,i-1)\operatorname{and} f(i+1,k)$ 的值只有 $\log^2 V$ 种，可以对每种 $O(n)$ 暴力枚举 $j$ 处理。

如果交换两个关键点，暴力枚举后计算。

复杂度 $O(n\log^2 V)$。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxk=19,S=(1<<30)-1;
int n,m,T,ans;
int a[maxn],lg[maxn],st[maxk][maxn],pv[maxn],ispre[maxn],issuf[maxn],mx[maxn];
vector<int>pre,suf;
map<int,vector< pair<int,int> >>mp;
int query(int l,int r){
	if(l>r)
		return S;
	int k=lg[r-l+1];
	return st[k][l]&st[k][r-(1<<k)+1];
}
void calc(){
	pv[0]=S;
	for(int i=1;i<=n;i++)
		pv[i]=pv[i-1]&a[i];
	for(int i=n,v=S;i>1;i--){
		v&=a[i],ans=max(ans,pv[i-1]+v);
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n),ans=0,lg[0]=-1;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]),st[0][i]=a[i],lg[i]=lg[i>>1]+1,ispre[i]=issuf[i]=0;
		for(int i=1;i<=18;i++)
			for(int j=1;j+(1<<i)-1<=n;j++)
				st[i][j]=st[i-1][j]&st[i-1][j+(1<<(i-1))];
		pre.clear(),suf.clear();
		for(int i=1,now=S;i<=n;now&=a[i],i++)
			if((now&a[i])<now)
				pre.emplace_back(i),ispre[i]=1;
		for(int i=n,now=S;i>=1;now&=a[i],i--)
			if((now&a[i])<now)
				suf.emplace_back(i),issuf[i]=1;
		calc();
		for(int i=0;i<pre.size();i++)
			for(int j=0;j<suf.size();j++)
				swap(a[pre[i]],a[suf[j]]),calc(),swap(a[pre[i]],a[suf[j]]);
		mp.clear();
		for(int i=0;i<pre.size();i++)
			for(int j=pre[i];j<n;j++){
				int v=query(1,pre[i]-1)&query(pre[i]+1,j);
				mp[v].emplace_back(make_pair(j+1,query(j+1,n)&a[pre[i]]));
			}
		for(map<int,vector<pair<int,int>>>::iterator it=mp.begin();it!=mp.end();it++){
			int v=it->first;
			mx[n+1]=-2e9;
			for(int i=n;i>=1;i--){
				mx[i]=mx[i+1];
				if(issuf[i]==0)
					mx[i]=max(mx[i],v&a[i]);
			}
			vector<pair<int,int>>V=it->second;
			for(int i=0;i<V.size();i++)
				ans=max(ans,mx[V[i].first]+V[i].second);
		}
		mp.clear();
		for(int i=0;i<suf.size();i++)
			for(int j=1;j<suf[i];j++){
				int v=query(j+1,suf[i]-1)&query(suf[i]+1,n);
				mp[v].emplace_back(make_pair(j,query(1,j)&a[suf[i]]));
			}
		for(map<int,vector<pair<int,int>>>::iterator it=mp.begin();it!=mp.end();it++){
			int v=it->first;
			mx[0]=-2e9;
			for(int i=1;i<=n;i++){
				mx[i]=mx[i-1];
				if(ispre[i]==0)
					mx[i]=max(mx[i],v&a[i]);
			}
			vector<pair<int,int>>V=it->second;
			for(int i=0;i<V.size();i++)
				ans=max(ans,mx[V[i].first]+V[i].second);
		}
		printf("%d\n",ans);
	}
	return 0;
}