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

Beihai_Jiang · 2025-07-05 11:40:08 · 题解

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

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

题目描述

给定长度为 n 的整数数列 a，如果一个整数 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;
}