Solution P17725 | 轻舟万重山

BreakPlus · 2026-10-18 20:27:18 · 题解

太难了。

首先操作相当于把序列划分成若干段，每一段里面 xor 上任意一个数，最后整个序列要递增。

考虑每一个段 [l,r] 存在一个 x，使得 a_i \oplus x 递增的判定：a_i \oplus x \le a_{i+1} \oplus x 当且仅当 x 的二进制下第 \text{highbit}(a_i \oplus a_{i+1}) 位和 a_i 相同。

据此可以写出一个显然的贪心，但是问题在于最后一段有可能 x 可以是 0，这样答案就能少 1。

考虑 DP 来检查答案能不能少 1：令 f_i 表示 [1,i] 的最少划分段数，dp_i 表示在 [1,i] 中，划分段数量最少的情况下，最小的操作后的 a_i。

转移的时候考虑将所有 f_i = x 的点的 dp 转移到 f_i = x+1 的。

用一棵 01-trie 来维护所有合法的 x。具体的：

• 加入 dp_i 时，所有 dp_i \le a_{i+1} \oplus x 的 x 都变得可行；
• 加入 a_i \oplus x \le a_{i+1} \oplus x 的限制时，会要求 x 的二进制下某一位具体是多少。
• 算 dp_i 的时候查询 \min \limits_x (a_i \oplus x)。

第三种操作就是 01-trie 上从上到下走一遍。

首先如果第二种操作不会出现矛盾的限制的话（就是既限制第 k 位是 0，又限制第 k 位是 1），那么 01-trie 的任意一个高于第 k 位的子树是不会被删除的。

注意矛盾的限制并不意味着 trie 树被删空，因为有可能先加入限制再加入一个 dp_i。

于是可以直接暴力维护 01-trie，每次第二种操作时，直接把这一层的不合法点全都删掉，并顺便向上 pushup（如果父结点的子树被删空了，父结点也删掉，递归上去）。

但是这样递归到一个满的子树的时候（整个子树的 x 都被加入，显然在第一种操作时只在这里打了 tag，它是没有后代的），并不意味着这里面的 x 都合法，因为会有一些对更低位的限制。

因此我们要记录这个 01-trie 上每个结点子树内最晚加入的 dp_i，因为越晚加入，对它的限制就越松。

那么记录了时间戳以后有矛盾的限制也不怕了，直接处理出来以当前的 i 结尾，向左最长延伸到哪里，在 01-trie 上走的时候也要看一下最大时间戳能否满足要求。

这样查询就不均摊了，修改是均摊的，比题解区查询均摊，修改不均摊的做法难写多了，不建议学习。

// created time: 2026-10-18 14:35:52
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
#define popcnt __builtin_popcountll
const int mod = 998244353;
inline int gc(){
    static char buf[1<<20],*p=buf,*q=buf;
    if(p==q){
        q=(p=buf)+fread(buf,1,sizeof(buf),stdin);
        if(p==q) return EOF;
    }
    return *p++;
}
inline ll read(){
    ll x=0;int ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x;
}
inline int lg2(int x){ return 31^__builtin_clz(x); }
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
template<typename T>inline void addmod(T &x){ if(x >= mod) x -= mod; }
template<typename T>inline void chkmax(T &a,T b){ a=max(a,b); }
template<typename T>inline void chkmin(T &a,T b){ a=min(a,b); }
inline ll qpow(ll a,ll b){
    ll ans=1, base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod; b>>=1;
    }
    return ans;
}
inline ll INV(ll x){ return qpow(x, mod-2); }
const int INF=(1<<30),N=30000005;
int idx;
int n,a[1000005],f[1000005],bit[1000005],dp[1000005];

int son[N][2],vis[N],tag[N],fa[N],need;
vector<int>buc[30][2];
int dq[30][2];

void clear(){
    for(int i=1;i<=idx;i++) son[i][0]=son[i][1]=fa[i]=vis[i]=tag[i]=0;
    for(int i=0;i<30;i++)for(int o:{0,1}) dq[i][o]=0,buc[i][o].clear();
    idx=1; vis[0]=tag[0]=vis[1]=tag[1]=-1;
}

void color(int p,int v){ tag[p]=vis[p]=v; }
int create(int d,int v,int o){
    if(!son[v][o]){
        son[v][o]=++idx, fa[idx]=v;
        tag[idx]=vis[idx]=-1;
        buc[d][o].pb(idx);
    }
    int ret=son[v][o];
    return ret;
}
void pushup(int p){
    vis[p]=max({tag[p],vis[son[p][0]],vis[son[p][1]]});
}
void ins(int i){
    if(!dp[i]){ color(1,i); return; }
    if(dp[i]>=INF) return;
    // dp[i]-1<(a[i+1] xor x)
    int v=1;
    for(int d=29;d>=0;d--){
        int o=(a[i+1]>>d)&1,lim=((dp[i]-1)>>d)&1;
        if(!lim){
            color(create(d,v,o^1),i);
            v=create(d,v,o); 
        }else
            v=create(d,v,o^1);
    }
    for(v=fa[v];v;v=fa[v]) pushup(v);
}

void erase(int p){
    while(p){
        int old=vis[p];
        pushup(p);
        if(vis[p]==old) return;
        p=fa[p];
    }
}
int query(int w){
    int v=1,ans=0;
    if(vis[v]<=need) return INF;

    int lst=-1,DQ=need;
    for(int i=29;i>=0;i--){
        int o=((w>>i)&1);
        if(~tag[v]) chkmax(lst,tag[v]);
        if(max(lst,vis[son[v][o]])>max(dq[i][o],DQ)){
            v=son[v][o];
            chkmax(DQ,dq[i][o]);
        }else{
            ans^=(1<<i),v=son[v][o^1];
            chkmax(DQ,dq[i][o^1]);
        }
    }
    return ans;
}

void procedure(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read(),bit[i]=(a[i]==a[i-1]?-1:lg2(a[i]^a[i-1]));

    f[1]=1;
    int v0=0,v1=0;
    for(int i=2;i<=n;i++){
        f[i]=f[i-1];
        if(~bit[i]){
            if((~v0>>bit[i])&1) v0|=(1<<bit[i]), v1|=(a[i-1]&(1<<bit[i]));
            else if(((v1^a[i-1])>>bit[i])&1){
                f[i]++;
                v0=v1=0;
            }
        }
    }
    for(int m=1,r;m<=n;m=r+1){
        r=m; while(r<n&&f[r+1]==f[r]) ++r;
        int l=m-1; while(l>0&&f[l-1]==f[l]) --l;

        clear();
        memset(dq,-1,sizeof(dq));

        need=-1;
        for(int i=l+1;i<=r;i++){
            if(~bit[i]){
                int d=bit[i],v=(~a[i-1]>>d)&1;
                chkmax(dq[d][v],i-2);
                chkmax(need,dq[d][v^1]);
                for(int p: buc[d][v])
                    son[fa[p]][v]=0;
                for(int p: buc[d][v])
                    erase(fa[p]);
                vector<int>().swap(buc[d][v]);
            }
            if(i<=m){
                ins(i-1);
            }
            if(i>=m){
                dp[i]=query(a[i]);
            }
        }
    }
    for(int i=n-1;i>=0;i--){
        if(f[i]==f[n]-1 && dp[i]<=a[i+1]){
            printf("%d\n",f[n]-1);
            return;
        }
        if(a[i]>a[i+1])break;
    }
    printf("%d\n",f[n]);
}
int main(){
    #ifdef LOCAL
        assert(freopen("test.in","r",stdin));
        assert(freopen("test.out","w",stdout));
    #endif
    ll c=read(),T=read();
    // math_init();
    while(T--) procedure(),clear();
    return 0;
}