wa#10求助,hack过了
查看原帖
wa#10求助,hack过了
816821
Liyunze123楼主2025/2/6 17:02
#include<bits/stdc++.h>
#define M (l+r)/2
using namespace std;
int n,a[100010],st[100010][20],lo[100010],tr[100010*31][2],idx,ma[100010*31],rt[100010],m,ans;
void ins(int i,int pr,int k){
	ma[k]=i;
	for(int w=30;w>=0;w--){
		int x=a[i]>>w&1;
		if(pr)tr[k][x^1]=tr[pr][x^1];
		tr[k][x]=++idx,ma[idx]=i,k=tr[k][x],pr=tr[pr][x];
	}
}
int query(int l,int r,int v){
	int ans=0,i=rt[r];
	for(int w=30;w>=0;w--){
		int x=v>>w&1;
		ans<<=1;
		if(ma[tr[i][x^1]]>=l)ans|=x^1,i=tr[i][x^1];
		else ans|=x,i=tr[i][x];
	}
	return ans^v;
}
int ST(int l,int r){int k=lo[r-l+1];return max(st[l][k],st[r-(1<<k)+1][k]);}
int main(){
	scanf("%d",&n),rt[0]=++idx,ma[0]=-1,ins(0,0,rt[0]);
	for(int w=1;w<=n;w++)scanf("%d",&a[w]),m=max(m,a[w]),st[w][0]=a[w],rt[w]=++idx,ins(w,rt[w-1],rt[w]);
	for(int w=2;w<=n;w++)lo[w]=lo[w/2]+1;
	for(int x=1;x<=lo[n];x++)for(int w=1;w+(1<<x)-1<=n;w++)st[w][x]=max(st[w][x-1],st[w+(1<<(x-1))][x-1]);
	for(int w=1;w<=n;w++){
		if(a[w]==m)continue;
		int l=1,r=w-1,l1=0,l2=0,r1=n+1,r2=n+1;
		while(l<=r)if(ST(M,w-1)>a[w])l1=M,l=M+1;else r=M-1;
		l=1,r=l1-1;
		while(l<=r)if(ST(M,l1-1)>a[w])l2=M,l=M+1;else r=M-1;
		l=w+1,r=n;
		while(l<=r)if(ST(w+1,M)>a[w])r1=M,r=M-1;else l=M+1;
		l=r1+1,r=n;
		while(l<=r)if(ST(r1+1,n)>a[w])r2=M,r=M-1;else l=M+1;
		ans=max(ans,max(query(l2+1,r1-1,a[w]),query(l1+1,r2-1,a[w])));
	}
	printf("%d",ans);
	return 0;
}
2025/2/6 17:02
加载中...