考虑贪心，显然只要考虑相邻的数异或后的大小关系
对于数 $A[i],A[i+1]$，要保证它们之间的大小关系，显然要且仅要考虑它们最高的相异位
如果 $A[i]$ 最高相异位为 $0$，那么 $ans$ 此位必须为 $0$
反之 $ans$ 此位必须为 $1$
然后随便维护一下就好了，注意特判 $A[i]=A[i+1]$ 的情况
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e6+7; int n,m,a[N],f[33][2]; inline void ins(int pos,int k) { if(!pos||pos==n) return; if(a[pos]==a[pos+1]) return; int p=31; while( ((a[pos]>>p)&1) == ((a[pos+1]>>p)&1) ) p--; f[p][ (a[pos]>>p)&1 ]+=k; } inline int cnt() { int res=0; for(int i=0;i<=31;i++) if(f[i][1]) { if(f[i][0]) return -1; res+=(1<<i); } return res; } int main() { freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<n;i++) ins(i,1); printf("%d ",cnt()); m=read(); int x,y; while(m--) { x=read(),y=read(); ins(x,-1); ins(x-1,-1); a[x]=y; ins(x,1); ins(x-1,1); printf("%d ",cnt()); } return 0; }