题解：CF2247D2 XOR Sorting (Hard Version)

· · 题解

压哨失败 /hec

一天之内这样的戏码上演两次我无疑是高兴的。

假定你会弱化。

弱化这个东西更直观的证明是，考虑扔到 trie 上看，每次都是把阈值以下的部分任意交换，高于阈值的结构被锁死不能动。

那这里带修一样在 trie 上考虑就好了。

对下标开 trie，维护子树两个最值，然后对于左右必须交换的情况给自己打个标记，然后维护标记即可。

动态维护每个深度的标记数量增减，这样直接找到最浅的没有标记的深度即可求出答案。

复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define eps (1e-12)
#define inf ((int)1e18)
#define lowbit(x) ((x)&(-(x)))
#define mod 998244353
#define int long long
#define N 100005
using namespace std;
inline char get_char(bool op);
inline int read();
inline void print(int x);
inline int qpow(int a,int b=mod-2);
inline int gcd(int a,int b);
int t[25];
bool vis[3000005];
int dep[3000005];
int tr[3000005][2];
int a[3000005];
int mx[3000005];
int mn[3000005];
bool is[3000005];
int tp;
void init(){
    for(int i=0;i<=tp;i++)
    mx[i]=mn[i]=is[i]=tr[i][0]=tr[i][1]=dep[i]=vis[i]=0;
    tp=0;
    memset(t,0,sizeof t);
}
void ins(int x,int v){
    int flc=0;
    for(int i=19;i>=0;i--){
        int qwq=(x>>i)&1;
        if(!tr[flc][qwq])
        tr[flc][qwq]=++tp;
        dep[tr[flc][qwq]]=dep[flc]+1;
        flc=tr[flc][qwq];
    }
    a[flc]=v;
    is[flc]=1;
}
void dfs(int x){
    if(is[x]){
        mx[x]=mn[x]=a[x];
        return;
    }
    mx[x]=0;
    mn[x]=1e9;
    if(tr[x][0])dfs(tr[x][0]),mx[x]=max(mx[x],mx[tr[x][0]]),mn[x]=min(mn[x],mn[tr[x][0]]);
    if(tr[x][1])dfs(tr[x][1]),mx[x]=max(mx[x],mx[tr[x][1]]),mn[x]=min(mn[x],mn[tr[x][1]]);
    if(tr[x][0]&&tr[x][1]&&mx[tr[x][0]]>mn[tr[x][1]])t[dep[x]]++,vis[x]=1;
}
void upd(int p,int x,int v,int id){
    if(is[p]){
        mx[p]=mn[p]=a[p]=v;
        return;
    }
    int qwq=(x>>id)&1;
    upd(tr[p][qwq],x,v,id-1);
    mx[p]=0;
    mn[p]=1e9;
    if(tr[p][0])mx[p]=max(mx[p],mx[tr[p][0]]),mn[p]=min(mn[p],mn[tr[p][0]]);
    if(tr[p][1])mx[p]=max(mx[p],mx[tr[p][1]]),mn[p]=min(mn[p],mn[tr[p][1]]);
    if(tr[p][0]&&tr[p][1]&&mx[tr[p][0]]>mn[tr[p][1]]){
        if(!vis[p])
        t[dep[p]]++,vis[p]=1;
    }else if(vis[p])t[dep[p]]--,vis[p]=0;
}
inline void solve(){
    init();
    int n=read(),q=read();
    for(int i=0;i<n;i++){
        int x=read();
        ins(i,x);
    }
    dfs(0);
    int sum=0;
    for(int i=0;i<=19;i++){
        if(t[i]){
            sum=1<<(18-i+1);
            break;
        }
    }
    print(sum),puts("");
    while(q--){
        int id=read(),x=read();
        upd(0,id,x,19);
        int sum=0;
        for(int i=0;i<=19;i++){
            if(t[i]){
                sum=1<<(18-i+1);
                break;
            }
        }
        print(sum),puts("");
    }
}
signed main(){
    int t=1;
    t=read();
    while(t--)solve();
    return 0;
}
inline int gcd(int a,int b){
    int flc=min(__builtin_ctz(a),__builtin_ctz(b)),tmp;
    b>>=__builtin_ctz(b);
    while(a){
        a>>=__builtin_ctz(a);
        tmp=b-a;
        if(a<b)b=a;
        a=abs(tmp);
    }
    return (b<<flc);
}
inline char get_char(bool op=0){
    if(op)return getchar();
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int sum=0,fish=1;
    char c=get_char();
    while((c<'0'||c>'9')&&c!='-')c=get_char();
    if(c=='-')fish=-1,c=get_char();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=get_char();
    return sum*fish;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}