[ROI 2017 Day 1] 排序幻觉 题解

FFTotoro · 2024-06-28 21:38:06 · 题解

感觉完全不到蓝题。下文 \oplus 表示按位异或。

考虑把所有的条件拆开来处理最后再合并，即考虑确定 x,y 时，一个非负整数 b 满足(x\oplus b)\le(y\oplus b) 的充要条件是什么：

• 当 x=y 时，显然 b 可以取全体非负整数；
• 当 x\ne y 时，考虑 c=x\oplus y 在二进制下的最高位 \mathrm{highbit}(c)（即 x 和 y 最高的不相同的位），显然 b 在这一位的取值决定了 x 和 y 的大小，故如果 x<y 那么 b 该位应为 0，否则为 1；b 的其他位可以随便取。

于是对于每个 x=a_{i-1},y=a_i 考虑 b 的取值；把所有条件联立起来发现 b 的某些位的值已经确定了，但是有可能某两个条件会冲突，即一个要求 b 的某一位为 1 另一个要求为 0，此时就不存在符合条件的 b；否则先满足所有的条件，其他所有位都取 0 即可求出最小的 b。

修改操作是容易的，只需要把原来相邻的两对数（(a_{p-1},a_p) 和 (a_p,a_{p+1})）的条件撤销，修改之后再加上新的条件即可。令 V=\max a_i，则时间复杂度为 O(n+q\log V)，只要实现不是很差 2\mathrm{s} 随便过。

求 \mathrm{highbit} 可以借助 __builtin_clz 函数，该函数可以返回一个无符号整数二进制表示下前导零的个数（默认是 32 位的，__builtin_clzll 则是 64 位的）；所以用 31 减去其值，即可得到一个二进制数的最高位是从右往左的第几个位置。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n);
  for(auto &i:a)cin>>i;
  vector<array<int,2> > c(31);
  auto f=[&](int p,int d){
    if(int r=a[p-1]^a[p];r)
      c[31-__builtin_clz(r)][a[p-1]>a[p]]+=d;
  }; // 加入（d = 1）/ 撤销（d = -1）一个条件
  auto r=[&](){
    int w=0;
    for(int i=0;i<31;i++)
      if(c[i][1]){
        if(c[i][0])return -1; // 矛盾
        w|=1<<i; // 该位需要为 1
      }
    return w;
  }; // 求解最小的 b
  for(int i=1;i<n;i++)
    f(i,1); // 初始化
  cout<<r()<<'\n';
  int q; cin>>q;
  while(q--){
    int p,x,c=0; cin>>p>>x,p--;
    if(p<n-1)f(p+1,-1); if(p)f(p,-1); // 撤销
    if(a[p]=x;p<n-1)f(p+1,1); if(p)f(p,1); // 加入
    cout<<r()<<'\n';
  }
  return 0;
}