题意
给一个非负整数序列，每次问能否异或上一个正整数使得所有的数单调不减。如果能，输出最小的x，否则输出-1。单点修改。多测。要求最多一个log。
思考
只要考虑相邻的两个数。找到这两个数最高的不同的一位，那么只要考虑是一定要异或或者是一定不要异或。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1E6+5; 4 const int base=30; 5 int n,m; 6 int a[maxn],bucket[55][2]; 7 inline int read() 8 { 9 char ch=getchar(); 10 while(!isdigit(ch)) 11 ch=getchar(); 12 int sum=ch-'0'; 13 ch=getchar(); 14 while(isdigit(ch)) 15 { 16 sum=sum*10+ch-'0'; 17 ch=getchar(); 18 } 19 return sum; 20 } 21 void write(int x) 22 { 23 if(x>=10) 24 write(x/10); 25 putchar('0'+x%10); 26 } 27 inline void writen(int x) 28 { 29 if(x<0) 30 putchar('-'),x=-x; 31 write(x); 32 putchar('\n'); 33 } 34 inline int highbit(int x) 35 { 36 for(int i=base;i>=0;--i) 37 if(x&(1<<i)) 38 return i; 39 } 40 inline void add(int x,int y,int v) 41 { 42 if(x==y) 43 return; 44 bucket[highbit(x^y)][x>y]+=v; 45 } 46 inline void solve() 47 { 48 int sum=0; 49 for(int i=0;i<=base;++i) 50 { 51 if(bucket[i][0]&&bucket[i][1]){sum=-1;break;} 52 else if(bucket[i][1]) 53 sum+=(1<<i); 54 } 55 writen(sum); 56 } 57 int main() 58 { 59 ios::sync_with_stdio(false); 60 n=read(); 61 for(int i=1;i<=n;++i) 62 a[i]=read(); 63 for(int i=1;i<n;++i) 64 add(a[i],a[i+1],1); 65 m=read(); 66 solve(); 67 while(m--) 68 { 69 int x=read(),y=read(); 70 if(x!=1) 71 add(a[x-1],a[x],-1); 72 if(x!=n) 73 add(a[x],a[x+1],-1); 74 a[x]=y; 75 if(x!=1) 76 add(a[x-1],a[x],1); 77 if(x!=n) 78 add(a[x],a[x+1],1); 79 solve(); 80 } 81 return 0; 82 }