引入
咕了三天，开始补博客。先写今天的比赛吧，考的有些迷，所以不出意外地爆零了。
T1
- n的范围在1e6，所以说会\(n^2*log_2n\)算法的鸽鸽们，咱们是一样的，50分滚蛋了。（其实50暴力分已经很友好很友好了）。其实就是每次枚举位数，从高位到低位，依次判断答案应该去多少。
- 本人属于考试比较sb型的，就想杠一下第一题正解。想来想去，好像想到了一个\(n^2*log_2n^2\)的算法！就是如果当前一个区间的数如果大小还没分出来的时候，判断这个区间的最高位是否是一段连续的0和1则可以判断是否有解。正确性是显然的，但是具体如何维护这个01串我没有什么好的思路。当时想用树状数组前缀维护，但发现区间合并不好做。所以这是伪的80，所以我暴毙了。
- 100分做法显然是\(log_2n\)的或者线性的。我们考虑一个序列1~n按照从小到大的顺序，等价于每一个（i，i+1），a[i]<a[i+1]。这样的话，当我们修改一个数的值的时候，是不是好维护一些啊（\(log_2n\)的修改很容易做到吧）？
- 莫急，我们先讲一下需要维护什么。两个数，我们从高位向低位枚举，如果相同就继续，如果遇到了第一个不同的位，那么一定是当前位异或上了一个数，使得a[i]<a[i+1]。因为我们知道了a[i]和a[i+1]当前位分别是什么，所以我们可以确定需要异或的那个数当前位应该为0还是1。定义一个f（i，0）和f（i，1）分别代表被异或的数的第i为被要求为0的次数，被要求为1的次数。如果两个值都>0就直接输出-1，因为冲突了。否则就把每一位为1的异或上。修改就很显然了。
- 邱宇好强啊orz
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int lim=30;
int n,q,ans,a[N],f[N][2],power[N];bool flag;
int read(){
char ch=getchar();int num=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}
return num*f;
}
void add(int x,int y,int val){
for(int i=lim;i>=0;--i){
if(((x>>i)&1)==0){
if(((y>>i)&1)==1){
f[i][0]+=val;
break;
}
}else{
if(((y>>i)&1)==0){
f[i][1]+=val;
break;
}
}
}
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
n=read();power[0]=1;
for(int i=1;i<=30;++i) power[i]=power[i-1]*2;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<n;++i){
add(a[i],a[i+1],1);
}
flag=0,ans=0;
for(int i=lim;i>=0;--i){
if(f[i][0]>0&&f[i][1]>0) flag=1;
else if(f[i][1]>0) ans+=power[i];
}
if(flag) printf("-1\n");
else printf("%d\n",ans);
q=read();
while(q--){
int x,c;x=read(),c=read();
if(x<n)
add(a[x],a[x+1],-1);
if(x>1)
add(a[x-1],a[x],-1);
a[x]=c;
if(x<n)
add(a[x],a[x+1],1);
if(x>1)
add(a[x-1],a[x],1);
flag=0,ans=0;
for(int i=lim;i>=0;--i){
if(f[i][0]>0&&f[i][1]>0) flag=1;
else if(f[i][1]>0) ans+=power[i];
}
if(flag) printf("-1\n");
else printf("%d\n",ans);
}
return 0;
} T2
正解确实不是太好像，这里只提供一下40分的思路吧。
- solution
T3
打不过打不过