题解：CF2247D2 XOR Sorting (Hard Version)
Wandou666
·
·
题解
题意
交换 a_i，a_j 代价为 i \oplus j，求将数组排好序中所有代价最大值的最小，随后给出 q 次不可逆单点修改，并求出修改后序列的代价。
题解
::::info[回顾]
前情提要。
简单提一嘴 Easy Version，我们得到最终交换两个数的代价最小值一定是 2^p，其中 p 是这两个数的最高不同位，然后我们又发现形如 [x2^{p+1},(x+1)2^{p+1}) 的区间任意交换这里面两个数代价不超过 2^p，于是我们可以枚举最终贡献，比较前一个区间的最大和后一个区间最小值即可。
::::
有了 Easy Version 的做法，Hard Version 如喝水。
下面的区间指的是形如 [x2^{p+1},(x+1)2^{p+1}) 的区间。
我们发现一次修改只会影响 \log n 个区间，于是我们可以先预处理每个长度区间不符合要求相邻区间对的个数，然后线段树区间修改每一个区间，修改完判断一下就行，复杂度 O(n\log n +q \log ^2 n)。
我们令 $mx_{i,j}，mn_{i,j}$ 表示长度为 $2^j$ 的第 $i $ 个区间的最大值和最小值。
我们发现这个区间成某种神秘的递推关系，区间长度为 $2^p$ 所以我们可以只修改最小的长度为 $1$ 贡献为 $0 $ 的区间，然后对于长度为 $2^p$ 的第 $k$ 个区间，他新最值为 $\max\{mx_{p-1,k\times2},mx_{p-1,k\times2+1}\}$ 和$\min\{mn_{p-1,k\times2},mn_{p-1,k\times2+1}\}$。
于是我们得到了单次 $O(\log n)$ 的 $O((n+q)\log n)$ 写法。
或许你可以发现这货类似线段树，但是还是和线段树有区别的，最后就是会有一些块不满 $2^p$ 记得边界处理。
::::info[代码]
```cpp
//千万记得判边界
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],q;
int mx[25][N],mn[25][N],cnt[25];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
void update(int x,int d){
if(x>0&&mx[0][x-1]>mn[0][x])cnt[0]--;//处理旧答案
if(x<n-1&&mx[0][x]>mn[0][x+1])cnt[0]--;
a[x]=d;
mx[0][x]=mn[0][x]=d;
if(x>0&&mx[0][x-1]>mn[0][x])cnt[0]++;
if(x<n-1&&mx[0][x]>mn[0][x+1])cnt[0]++;//处理新答案
for(int i=1;i<=20;i++){
int len=1<<i;//这块大小
int k=x/len;
int tot=(n+len-1)/len;//块数，千万要上取整
if(k>=tot)break;
if(k>0&&mx[i][k-1]>mn[i][k])cnt[i]--;
if(k<tot-1&&mx[i][k]>mn[i][k+1])cnt[i]--;
int mid=k*len+len/2;//边界处理
if(mid>=n)mx[i][k]=mx[i-1][ls(k)],mn[i][k]=mn[i-1][ls(k)];
else mx[i][k]=max(mx[i-1][ls(k)],mx[i-1][rs(k)]),mn[i][k]=min(mn[i-1][ls(k)],mn[i-1][rs(k)]);
if(k>0&&mx[i][k-1]>mn[i][k])cnt[i]++;
if(k<tot-1&&mx[i][k]>mn[i][k+1])cnt[i]++;
}
}
int query(){
for(int i=0;i<=20;i++){
if(cnt[i]==0)return (i==0?0:(1<<(i-1)));
}
return 1<<20;
}
int main(){
cin.tie(0);ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--){
cin>>n>>q;
for(int i=0;i<=20;i++)cnt[i]=0;
for(int i=0;i<n;i++){
cin>>a[i];
mx[0][i]=mn[0][i]=a[i];
}
for(int i=1;i<=20;i++){
int len=1<<i;
int tot=(n+len-1)/len;
if(tot==0)break;
for(int j=0;j<tot;j++){
int mid=j*len+len/2;//边界处理，就是如果j是后面不完整的直接继承
if(mid>=n)mx[i][j]=mx[i-1][ls(j)],mn[i][j]=mn[i-1][ls(j)];
else mx[i][j]=max(mx[i-1][ls(j)],mx[i-1][rs(j)]),mn[i][j]=min(mn[i-1][ls(j)],mn[i-1][rs(j)]);
}
}
for(int i=0;i<=20;i++){
int len=1<<i;
int tot=(n+len-1)/len;
for(int j=0;j<tot-1;j++){
if(mx[i][j]>mn[i][j+1])cnt[i]++;
}
}
cout<<query()<<'\n';
while(q--){
int x,d;
cin>>x>>d;
update(x,d);
cout<<query()<<'\n';
}
}
return 0;
}
```
::::