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

· · 题解

首先根据异或的性质，我们发现这个题是给序列划分若干个区间，然后每个区间异或同一个值，要求区间内有序，区间断点处有序。

然后我们考虑会异或最后一段，那么我们可以给第 i 段异或上一个类似于 2^{100 + i} 的东西，然后段之间就保证有序了，只要求段内可以通过异或摸一个值变得有序。

这个的限制是简单的，我们去找满足 a_i \oplus x \le a_{i + 1} \oplus x 的 x 满足什么性质，我们可以找到 a_i \oplus a_{i + 1} 的 \operatorname{highbit}，x 在这一位上必须和 a_i 相同，于是我们开一个位数的桶，统计是否冲突即可。同时记录前 i 个数最少的分段数 dp_i。

这一部分时间复杂度 O(n)。

然后我们发现可能最后一段不操作，这样可能使答案减小一，但值域有了限制，考虑 dp。

设 f_{i,j} 表示前 i 个数，分了 j 段，此时最后一个数的最小值，直接转移是 O(n^3 \log V) 的。

然后其实数组中大量的数是无意义的，我们只关心 f_{i,dp_i} 的值，于是直接扔掉一维，令 f_i 表示前 i 个分成 dp_i 段，最后一个数的最小值。

然后状态没啥可优化的了，考虑优化转移。

考虑去刻画转移过程，用 trie 维护能供转移的 x。

首先，在断点处，往 trie 里加入所有满足 a \oplus x \ge b 的 x。

然后中间会产生新限制，及删掉第 k 位是 v 的数。

最后，需要查询 trie 里最小的 a \oplus x。

第一个操作我们发现可以通过打 tag 延迟建新点的方式做到，第二个操作可以通过维护全局时间戳来做到，最后一个就是基本功了。

总时间复杂度 O(n \log V)。实现臭了可能会被卡常。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uni unsigned int
#define ull unsigned long long
#define lll __int128
#define ld long double
#define pb push_back
#define mk make_pair
#define ppcnt __builtin_popcount
#define clz __builtin_clzll
const int inf=1<<30;
ll read()
{
    ll k=0,f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return f?-k:k;
}
void write(string s){for(char c:s)putchar(c);}
int St[100],Top;
void write(int x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar('0'+St[Top--]);
}
void write(ll x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar('0'+St[Top--]);
}
int n,a[1000010];
int l[1000010],r[1000010],dp[1000010],b[50];
int highbit(ll x){return 63-clz(x);}
namespace Trie
{
    struct Node
    {
        int son[2],tag;
    }t[100000010];
    int cnt=0,bin[100000010],top=0;
    int tim[50][2],pre[50];
    int newnode()
    {
        int p=top?bin[top--]:++cnt;
        t[p].tag=-2;
        t[p].son[0]=t[p].son[1]=0;
        return p;
    }
    void del(int p)
    {
        if(!p)return;
        del(t[p].son[0]),del(t[p].son[1]);
        t[p].son[0]=t[p].son[1]=0;
        bin[++top]=p;
    }
    void assign(int p,int ti)
    {
        t[p].tag=ti;
        del(t[p].son[0]),del(t[p].son[1]);
        t[p].son[0]=t[p].son[1]=0;
    }
    void pushdown(int p)
    {
        del(t[p].son[0]);
        t[p].son[0]=newnode();
        t[t[p].son[0]].tag=t[p].tag;
        del(t[p].son[1]);
        t[p].son[1]=newnode();
        t[t[p].son[1]].tag=t[p].tag;
        t[p].tag=-1;
    }
    void insert(int p,int x,int y,int dep,int ti)
    {
        if(dep==-1||!(y&((1<<(dep+1))-1)))
        {
            assign(p,ti);
            return;
        }
        int c=(x>>dep)&1,cy=(y>>dep)&1;
        if(t[p].tag>=0)pushdown(p);
        if(t[p].tag==-2)t[p].tag=-1;
        if(cy==0)
        {
            if(!t[p].son[c^1])t[p].son[c^1]=newnode();
            assign(t[p].son[c^1],ti);
        }
        if(cy==1)c^=1;
        if(!t[p].son[c])t[p].son[c]=newnode();
        insert(t[p].son[c],x,y,dep-1,ti);
    }
    void addtag(int c,int dep,int ti)
    {
        tim[dep][c]=ti;
        int v=min(tim[dep][0],tim[dep][1]);
        for(int i=dep;i<=30&&pre[i]<v;i++)pre[i]=v;
    }
    int query(int p,int x,int dep,int ti)
    {
        if(t[p].tag==-2)return inf;
        if(t[p].tag>=0)
        {
            if(t[p].tag<ti||(dep>=0&&t[p].tag<pre[dep]))
            {
                assign(p,-2);
                return inf;
            }
            int ans=0,v;
            for(int i=dep;i>=0;i--)
            {
                v=(x>>i)&1;
                if(t[p].tag<tim[i][v])ans|=1<<i;
            }
            return ans;
        }
        if(dep==-1)
        {
            assign(p,-2);
            return inf;
        }
        int res=inf,c=(x>>dep)&1;
        if(t[p].son[c])res=query(t[p].son[c],x,dep-1,max(ti,tim[dep][c]));
        if(res!=inf)return res;
        c^=1;
        if(t[p].son[c])res=query(t[p].son[c],x,dep-1,max(ti,tim[dep][c]));
        if(res!=inf)return res|(1<<dep);
        assign(p,-2);
        return inf;
    }
    void Clear()
    {
        cnt=top=0;
        t[0].son[0]=t[0].son[1]=0;
        t[0].tag=-2;
        memset(tim,0,sizeof(tim)),memset(pre,0,sizeof(pre));
    }
}using namespace Trie;
int f[1000010];
void solve()
{
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    int cnt=1;
    memset(b,-1,sizeof(b));
    l[0]=r[0]=0;
    l[1]=dp[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(a[i]!=a[i-1])
        {
            int v=a[i]^a[i-1],h=highbit(v);
            v=(a[i]>>h)&1;
            if(b[h]==-1)b[h]=v;
            else if(b[h]!=v)
            {
                memset(b,-1,sizeof(b));
                r[cnt]=i-1;
                ++cnt;
                l[cnt]=i;
            }
        }
        dp[i]=cnt;
    }
    r[cnt]=n;
    for(int i=1;i<=n;++i)f[i]=-1;
    f[0]=0;
    for(int i=1;i<dp[n];i++)
    {
        Clear();
        for(int j=l[i-1];j<=r[i-1];j++)
        {
            if(j>l[i-1]&&a[j]!=a[j+1])
            {
                int v=a[j]^a[j+1],h=highbit(v);
                addtag(((a[j]>>h)&1)^1,h,j+1);
            }
            if(f[j]!=-1&&f[j]!=inf)insert(0,a[j+1],f[j],30,j+1);
        }
        for(int j=l[i];j<=r[i];j++)
        {
            f[j]=query(0,a[j],30,0);
            if(a[j]!=a[j+1])
            {
                int v=a[j]^a[j+1],h=highbit(v);
                addtag(((a[j]>>h)&1)^1,h,j+1);
            }
        }
    }
    int ans=dp[n],limit=n;
    for(int i=n-1;i>=1;i--)
    {
        if(a[i]<=a[i+1])limit=i;
        else break;
    }
    for(int i=max(l[dp[n]-1],limit-1);i<=r[dp[n]-1];i++)
    {
        if(f[i]!=-1&&f[i]<=a[i+1])
        {
            ans=dp[n]-1;
            break;
        }
    }
    write(ans),putchar('\n');
}
int main()
{
    // freopen("rain.in","r",stdin);
    // freopen("rain.out","w",stdout);
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int C=read(),T=read();
    while(T--)solve();
    return 0;
}