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

IntoTheDusk · 2026-08-11 13:30:42 · 题解

先考虑静态问题怎么做。

单调不降的限制实质上等价于相邻两数之间不降。于是对于 1 \sim n-1 的每一个 i，我们考虑 a_i 和 a_{i+1} 的大小关系。取 x=a_i,y=a_{i+1}

• 若 x=y，则对于 d 没有要求。
• 若 x>y，我们在二进制下从高到低找到第一个 x,y 不相同的位置，则在这个位置上 x 为 1，y 为 0。为了满足单调性，我们必须让 d 在这一位上为 1。
• 若 x<y，类似第二种情况，我们找出从高到低第一个不相同的位置，则 d 的这个位置上必须为 0。

现在，我们得到了至多 n-1 条限制，每条限制形如「d 的某一位必须是 0/1」。令 b_i 表示是否有某一条限制要求 d 的第 i 位为 1，c_i 表示是否有某一条限制要求 d 的第 i 位为 0，我们分类讨论：

• 若 c_i=b_i=1，则必定无解。
• 若 b_i=1,c_i=0，则 d 的第 i 位必定为 1。
• 否则，我们都可以填 0。

现在考虑动态问题怎么做。注意到单点修改只会影响到至多两个相邻对，而这只会影响 d 的至多两个位。于是就做完了，时间复杂度 \mathcal{O}\left(n\log n+q\right)。

下面的代码是直接重构的，复杂度为 \mathcal{O}\left((n+q)\log n\right)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int INF=1e18;
const int B=33;
const int V=40;
int n,q,a[N],posb[N],posc[N];
int b[V],c[V];
int kth(int n,int k){
    return (n>>k)&1ll;
} 
void add(int i){
    if(a[i]>a[i+1]){
        for(int j=B;j>=0;j--){
            if(kth(a[i],j)!=kth(a[i+1],j)){
                b[j]++;
                posb[i]=j;
                break;
            }
        }
    }
    else if(a[i]<a[i+1]){
        for(int j=B;j>=0;j--){
            if(kth(a[i],j)!=kth(a[i+1],j)){
                c[j]++;
                posc[i]=j;
                break;
            }
        }
    }
}
void del(int i){
    if(posb[i]!=-1){
        b[posb[i]]--;
        posb[i]=-1;
    }
    if(posc[i]!=-1){
        c[posc[i]]--;
        posc[i]=-1;
    }
}
int Q(){
    int ans=0;
    for(int i=B;i>=0;i--){
        if(b[i]&&c[i]){
            return -1;
        }
        if(b[i]){
            ans+=(1ll<<i);
        }
    }
    return ans;
}
signed main(){
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        posb[i]=posc[i]=-1;
        add(i);
    }
    cout<<Q()<<'\n';
    cin>>q;
    while(q--){
        int pos,v;cin>>pos>>v;
        if(pos<n) del(pos);
        if(pos>1) del(pos-1);
        a[pos]=v;
        if(pos<n) add(pos);
        if(pos>1) add(pos-1);
        cout<<Q()<<'\n';
    }
    return 0;
}