题解：P17725 [SCP-S 2026] 大雨 / rain

ty_mxzhn · 2026-10-22 19:40:58 · 题解

题目链接。

考虑 a_n=0 的部分分，此时如果 a_n 不被修改，则所有数都要被改为 0，这是平凡情况，判一下就好。

否则 a_n 会被修改。把每一段的极高位（>30）修改使得我们不需要考虑相邻段之间的贡献。

段内，考虑任意的 a_i,a_{i+1}，对于这一段涉及的异或 x，只需要 x 的第 \mathrm{highbit}(a_i\oplus a_{i+1}) 是 0/1 即可。限制是单调的，双指针即可。

记这样求得的答案为 w，我们只需要判断真实答案是不是 w-1 即可。

更进一步，我们给前 i 个数做划分，最后一个数是 j，段数是 g_{i,j}。显然 g_{i,j}\ge f_i。其中 f_i 是上面那个无限制的 dp 的段数。

若 g_{i,j}>f_i，则后面就算无限制，答案也只会求得 w 的答案。

所以我们只考虑 g_i 表示前 i 个数段数 =f_i 的方案中，最后一位的最小值。

考虑如何从 g_j\to g_i。先找出 [j+1,i] 中对 x 的限制。随后 g_j\le a_{j+1}\oplus x。在此基础上要最小化 a_i\oplus x。

钦定 g_j 和 a_{j+1}\oplus x 在高 p 位都是相同的，第 p+1 位 g_j 是 0，a_{j+1}\oplus x 是 1 即可。这显然又是一些限制。

对于被钦定的部分的合并可以用位运算。所以 O(n^2\log V) 可以写。拼上 a_n=0 有 76 分，赛时做到这就可以跑路了。

看眼题解，发现怎么直接在 trie 树上打标记就做完了。

还是从查询出发。如果总节点数足够少，查询时，如果我们走到一棵子树里，发现这棵子树里居然没有合法点，那就可以直接把这整棵子树删除了。均摊就是对的。

修改时，我们有一些子树是满的，我们把满的子树缩成一个点，这个点下方只考虑满的情况即可。

对于一个满点，记录其左端点 j，并且需要知道左端点 j 对应的限制。差分后，限制可以表示成两个二进制数，表示哪些位置不能是 0，哪些位置不能是 1。满点可以快速判断内部有没有合法点。如果没有就可以删去这个满点。

所以其实根本不需要打标记，其实就是维护虚树。。。

现在我们要知道 j 是否可以转移到 i。需要处理出 [j+1,i] 的所有限制，把禁用 0 和禁用 1 的限制分别找出即可，就是取 or。因为 dp_i=dp_j+1 所以这部分时间复杂度 O(n)。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;

namespace tymxz{
    const int N=1e6+7,LG=30;
    int n;
    int a[N],vs[N],L[N];
    int v[30][2],cnt;
    void work(int p,int x){
        int j=vs[p];
        if(j==-1) return;
        int o=(a[p]>>j)&1;
        if(v[j][0]&&v[j][1]) cnt--;
        v[j][o]+=x;
        if(v[j][0]&&v[j][1]) cnt++;
    }
    int dp[N],g[N];
    int trie[N*LG][2],tot;
    int c[N*LG];
    void chmax(int &x,int y){
        if(x<y) x=y;
    }
    void init(){
        tot=1;
        c[tot]=0;
    }
    void ins(int &r,int a,int b,int id){//a<=b^x
        if(r==0) r=tot=1,trie[tot][0]=trie[tot][1]=c[tot]=0;
        int p=1;
        for(int i=LG-1;i>=0;i--){
            int a1=(a>>i)&1,b1=(b>>i)&1;
            if(a1==0){
                if(!trie[p][b1^1]) trie[p][b1^1]=++tot,trie[tot][0]=trie[tot][1]=c[tot]=0;
                chmax(c[trie[p][b1^1]],id+1);
            }
            if(!trie[p][a1^b1]) trie[p][a1^b1]=++tot,trie[tot][0]=trie[tot][1]=c[tot]=0;
            p=trie[p][a1^b1];
        }
        chmax(c[p],id+1);
    }
    const int inf=(1<<30)+1;
    int dl[N][2],dr[N][2],nw,X,ans;
    int solve(int u,int v,int x,int y){
        if(dp[u]+1!=dp[v]) return inf;
        x|=dl[u][0]|dr[v][0];
        y|=dl[u][1]|dr[v][1];
        if(x&y) return inf;
        return (x^X)&(x|y);
    }
    void qry(int &p,int dep,int x,int y){
        if(p==0) return;
        if(c[p]>0){
            int j=c[p]-1;
            int w=solve(j,nw,x,y);
            if(w<inf) ans=min(ans,w);
            else c[p]=0;
        }
        if(dep==-1){
            if(c[p]==0) p=0;
            return;
        }
        int i=(X>>dep)&1;
        qry(trie[p][i],dep-1,x|((i!=0)<<dep),y|((i!=1)<<dep));
        if(trie[p][i]==0){
            i^=1;
            qry(trie[p][i],dep-1,x|((i!=0)<<dep),y|((i!=1)<<dep));      
        }
        if(trie[p][0]==0&&trie[p][1]==0&&c[p]==0) p=0;
        return;
    }
    inline int turn(int p,int o){
        p++;
        if(vs[p]==-1) return 0;
        if(o!=((a[p]>>vs[p])&1)) return 0;
        return (1<<vs[p]);
    }
    bool chk(){
        tot=0;
        int rt=0;
        for(int l=0;l<=n;){
            int r=l;
            while(r<=n&&dp[r]==dp[l]) r++;
            for(int i=l;i<r;i++){
                if(i>0){
                    nw=i,ans=inf,X=a[i];
                    qry(rt,LG-1,0,0);
                    g[i]=ans;
                }
            }
            rt=0;
            for(int i=l;i<r;i++){
                if(i<n){
                    if(g[i]<inf) ins(rt,g[i],a[i+1],i);
                }
            }
            l=r;
        }
        for(int i=n-1;i>=0;i--){
            if(dp[i]<dp[n]&&g[i]<=a[i+1]) return 1;
            if(a[i]>a[i+1]) return 0;
        }
        return 0;
    }
    void subt(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        cnt=0;
        for(int i=0;i<LG;i++) v[i][0]=v[i][1]=0;
        for(int i=2;i<=n;i++){
            if(a[i]!=a[i-1]) vs[i]=__lg(a[i]^a[i-1]);
            else vs[i]=-1;
        }
        int l=1;
        for(int i=1;i<=n;i++){
            if(i>1) work(i,1);
            while(l<i&&cnt>0) work(l+1,-1),l++;
            dp[i]=dp[l-1]+1;
            L[i]=l;
        }
        for(int i=0;i<=n;i++) for(int o=0;o<2;o++){
            if(i>1&&dp[i]==dp[i-1]) dr[i][o]=dr[i-1][o]|turn(i-1,o);
            else dr[i][o]=0;
        }
        for(int i=n;i>=0;i--) for(int o=0;o<2;o++){
            if(i<n&&dp[i]==dp[i+1]) dl[i][o]=dl[i+1][o]|turn(i+1,o);
            else dl[i][o]=0;
        }
        int ans=dp[n];
        if(chk()) ans--;
        cout<<ans<<endl;
    }
}
int c,t;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>c>>t;
    while(t--) tymxz::subt();
    return 0;
}

:::

因为没有打标记，所以比较好写。