自动搬运

查看原文

来自洛谷，原作者为

	Beihai_Jiang Eclipse first,the rest nowhere

搬运于2025-08-24 22:59:57，当前版本为作者最后更新于2025-07-05 11:40:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P10650 [ROI 2017] 排序幻觉 (Day 1)

[P10650 ROI 2017] 排序幻觉 (Day 1) - 洛谷

题目描述

给定长度为 $n$ 的整数数列 $a$，如果一个整数 $b$ 满足：

$$(a_1 \operatorname{xor} b) \le (a_2 \operatorname{xor} b) \le \dots \le (a_n \operatorname{xor} b) $$

则称 $b$ 是 $a$ 数列的幻数。

接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整数 $k_i$，每次修改都会对后面的询问产生影响。你需要求出第一次修改前以及每次修改后这个数列的最小的幻数是多少，特别的，如果不存在幻数请输出 $-1$。

Solution

对于 $a_i$ 和 $a_{i+1}$，在二进制上从高位到低位第一个不相同的位记为第 $k$ 位。

若 $a_i=a_{i+1}$，不做任何处理。因为两数无论异或何值都相等。

若 $a_{i}<a_{i+1}$，则 $b$ 二进制的第 $k$ 位一定为 $0$。否则会有 $a_i'>a_{i+1}'$。

若 $a_i>a_{i+1}$，则 $b$ 二进制的第 $k$ 位一定为 $1$。否则会有 $a_i'>a_{i+1}’$。

若 $b$ 的某一位一定为 $0$ 且一定为 $1$，则没有幻数，输出 $-1$。

注意修改 $a_u$ 后，只需更新 $a_{u-1},a_u$ 和 $a_u,a_{u+1}$ 的贡献。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q;
int a[N];
int b[2][35];
int ans,cnt;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++){
		if(a[i]==a[i+1]) continue;
		int temp=a[i]^a[i+1];
		int k=log2(temp);
		if(a[i]<a[i+1]){
			b[0][k]++;
			if(b[0][k]==1 && b[1][k]>0) cnt++,ans-=pow(2,k);
		}
		else{
			b[1][k]++;
			if(b[1][k]==1 && b[0][k]>0) cnt++;
			else if(b[1][k]==1) ans+=pow(2,k);
		}
	}
	if(cnt>0)
		cout<<-1<<"\n";
	else
		cout<<ans<<"\n";
	cin>>q;
	for(int i=1;i<=q;i++){
		int u,y;
		cin>>u>>y;
		if(u-1>0 && a[u-1]!=a[u]){
			int temp=a[u-1]^a[u];
			int k=log2(temp);
			if(a[u-1]<a[u]){
				b[0][k]--;
				if(!b[0][k] && b[1][k]>0) cnt--,ans+=pow(2,k);
			}
			else{
				b[1][k]--;
				if(!b[1][k] && b[0][k]>0) cnt--;
				else if(!b[1][k]) ans-=pow(2,k);
			}
		}
		if(u+1<=n && a[u]!=a[u+1]){
			int temp=a[u]^a[u+1];
			int k=log2(temp);
			if(a[u]<a[u+1]){
				b[0][k]--;
				if(!b[0][k] && b[1][k]>0) cnt--,ans+=pow(2,k);	
			}
			else{
				b[1][k]--;
				if(!b[1][k] && b[0][k]>0) cnt--;
				else if(!b[1][k]) ans-=pow(2,k);
			}
		}
		a[u]=y;
		if(u-1>0 && a[u-1]!=a[u]){
			int temp=a[u-1]^a[u];
			int k=log2(temp);
			if(a[u-1]<a[u]){
				b[0][k]++;
				if(b[0][k]==1 && b[1][k]>0) cnt++,ans-=pow(2,k); 
			}
			else{
				b[1][k]++;
				if(b[1][k]==1 && b[0][k]>0) cnt++;
				else if(b[1][k]==1) ans+=pow(2,k);
			}
		}
		if(u+1<=n && a[u]!=a[u+1]){
			int temp=a[u]^a[u+1];
			int k=log2(temp);
			if(a[u]<a[u+1]){
				b[0][k]++;
				if(b[0][k]==1 && b[1][k]>0) cnt++,ans-=pow(2,k); 
			}
			else{
				b[1][k]++;
				if(b[1][k]==1 && b[0][k]>0) cnt++;
				else if(b[1][k]==1) ans+=pow(2,k);
			}
		}
		if(cnt>0)
			cout<<-1<<"\n";
		else
			cout<<ans<<"\n";
	}
	return 0;
}