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

yimuhua · 2026-11-12 21:53:44 · 题解

先转化题意为：将序列分成若干段，每一段异或一个数，要求单调不降，求最小段数。其中可以有一个后缀不异或，不计入段数。

先不管那个后缀，假设得到了分段方法，考虑如何满足单调不降。对于相邻两段之间，注意到 x 没有限制，可以让 x_i 额外异或 2^{\inf+i}，这样段之间就没有限制。

对于段内，限制即 \exist x,\forall (i,i+1),a_i\oplus x\le a_{i+1}\oplus x。对于相邻两不同数，限制即 x 在两数最高不同位上必须与 a_i 相同。显然对每个右端点可以求出最左的合法开头位置。

那么如果不管最后的后缀，直接预处理然后 dp 即可，复杂度线性。

然后考虑可能不用最后一次，即要求是否存在 i，使得前缀 i 在分不超过 f_i 段时，存在合法的最后一段的 x，使得 a_i\oplus x\le a_{i+1}。

此时之前的段之间不能不管了，那么考虑求 g_i 表示前缀 i 合法分成 f_i 段，a_i\oplus x 最小是多少。最终只需判断是否存在 i 使得 f_i=f_n-1\land g_i\le a_{i+1}\land [i+1,n] 合法即可。

转移即 g_i\leftarrow \min\limits_{g_{j-1}\le a_j\oplus x,[j,i]\oplus x 合法,f_{j-1}+1=f_i}a_i\oplus x。那么扫描 i 时要维护所有 j 的合法 x 的并集，与 a_i 的最小异或和。

优化一下转移。第一个限制好办。第二个限制扫描到 i 时加入的限制是 x 在 a_{i-1},a_i 最高不同位的取值。第三个限制双指针 j 即可，注意这些 j 也要受前两个限制。

那么考虑在 \mathrm{trie} 上维护每个 x 的合法 j 个数。一操作是在 j 对所有 x\oplus a_j\ge g_{j-1} 的 x 加一，二操作是删除当前树中第 k 位为 v 的数。

一操作直接给子树打标记，记录加入时间，复杂度 O(\log V)。二操作维护每个 (k,v) 的最后删除时间。最后查询最小异或和，到一个点比较子树最晚加入时间和每个位删除时间即可，记得下传标记。

然后 f_{j-1}+1=f_i 的限制，把 f 按层开 \mathrm{trie} 即可。最终复杂度 O(n\log V)。

#include <bits/stdc++.h>
using namespace std;
namespace Fastio {
    const int L = 1 << 20;
    inline int gc() {
        static char buf[L], *l = buf, *r = buf;
        if(l == r)
            r = (l = buf) + fread(buf, 1, L, stdin);
        return l == r ? EOF : *l++;
    }
    char obuf[L], *p = obuf;
    inline void flush() {
        fwrite(obuf, 1, p - obuf, stdout), p = obuf;
    }
    inline void pc(char c) {
        if(p == obuf + L)
            flush();
        *p++ = c;
    }
    struct Reader {
        template <typename T>
        inline Reader& operator>>(T &x) {
            x = 0;
            int c = gc(), f = 1;
            while(c < '0' || c > '9') {
                if(c == '-')
                    f = -1;
                c = gc();
            }
            while(c >= '0' && c <= '9')
                x = x * 10 + c - '0', c = gc();
            x *= f;
            return *this;
        }
    }cin;
    struct Writer {
        template <typename T>
        inline Writer& operator<<(T x) {
            if(x < 0)
                pc('-'), x = -x;
            char s[24], *t = s + 24;
            while(x >= 100) {
                int lim = x % 100;
                x /= 100;
                *--t = lim % 10 + '0', *--t = lim / 10 + '0';
            }
            if(x < 10)
                *--t = x + '0';
            else
                *--t = x % 10 + '0', *--t = x / 10 + '0';
            int len = s + 24 - t;
            if(p + len > obuf + L)
                flush();
            memcpy(p, t, len), p += len;
            return *this;
        }
        inline Writer& operator<<(char c) {
            pc(c);
            return *this;
        }
        inline Writer& operator<<(const char *s) {
            while(*s)
                pc(*s++);
            return *this;
        }
        ~Writer() {
            flush();
        }
    }cout;
    #define cin Fastio::cin
    #define cout Fastio::cout
}
const int inf = 1 << 30;
int c, t, n, ans, a[1000005], f[1000005], lim[30];
struct Trie {
    int cnt, head, tot, rt[2], d[30][2], pre[30], to[32000005][2], tag[32000005];
    int build() {
        int x;
        if(head)
            x = head, head = to[x][0];
        else
            x = ++cnt;
        return to[x][0] = to[x][1] = tag[x] = 0, x;
    }
    void clear(int x) {
        if(!x)
            return;
        clear(to[x][0]), clear(to[x][1]), to[x][0] = head, head = x;
        return;
    }
    void addtag(int &x, int t) {
        if(!x)
            x = build();
        else
            clear(to[x][0]), clear(to[x][1]);
        to[x][0] = to[x][1] = 0, tag[x] = t;
        return;
    }
    void pushdown(int x) {
        if(tag[x])
            addtag(to[x][0], tag[x]), addtag(to[x][1], tag[x]), tag[x] = 0;
        return;
    }
    void insert(int &x, int v, int b, int k, int t) {
        if(!x)
            x = build();
        if(k < 0 || !(b & (1 << k + 1) - 1))
            return addtag(x, t);
        pushdown(x);
        int p = v >> k & 1, q = b >> k & 1;
        if(!q)
            addtag(to[x][p ^ 1], t);
        return insert(to[x][p ^ q], v, b, k - 1, t);
    }
    inline void del(int k, int x) {
        d[k][x] = ++tot;
        for(int i = k; i < 30; i++)
            pre[i] = max(pre[i], min(d[k][0], d[k][1]));
        return;
    }
    int query(int &x, int v, int k, int mx) {
        if(!x)
            return inf;
        if(tag[x]) {
            if(tag[x] <= mx || ~k && tag[x] <= pre[k])
                return clear(x), x = 0, inf;
            int s = 0;
            for(int i = k; ~i; i--)
                if(d[i][v >> i & 1] >= tag[x])
                    s |= 1 << i;
            return s;
        }
        if(!~k)
            return clear(x), x = 0, inf;
        int p = v >> k & 1, s = query(to[x][p], v, k - 1, max(mx, d[k][p]));
        if(s == inf && (s = query(to[x][p ^ 1], v, k - 1, max(mx, d[k][p ^ 1]))) < inf)
            s |= 1 << k;
        if(s == inf && !to[x][0] && !to[x][1])
            clear(x), x = 0;
        return s;
    }
    void init() {
        memset(d, 0, sizeof(d)), memset(pre, rt[0] = rt[1] = cnt = head = tot = 0, sizeof(pre));
        return;
    }
}T;
int main() {
    cin >> c >> t;
    while(t--) {
        cin >> n, fill(lim, lim + 30, -1), f[0] = 0, f[1] = 1;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        int last = 0;
        for(int i = 2; i <= n; i++) {
            f[i] = f[i - 1];
            if(a[i - 1] > a[i])
                last = i - 1;
            if(a[i - 1] ^ a[i]) {
                int k = __lg(a[i - 1] ^ a[i]);
                if(~lim[k] && lim[k] != (a[i - 1] >> k & 1))
                    f[i]++, fill(lim, lim + 30, -1);
                else
                    lim[k] = a[i - 1] >> k & 1;
            }
        }
        if(f[n] == 1) {
            cout << !!last << '\n';
            continue;
        }
        T.init(), ans = f[n];
        for(int i = 1, g = 0; i <= n; i++) {
            if(i > 1 && a[i - 1] != a[i]) {
                int k = __lg(a[i - 1] ^ a[i]);
                T.del(k, (a[i - 1] >> k & 1) ^ 1);
            }
            if(g < inf)
                T.insert(T.rt[1], a[i], g, 29, ++T.tot);
            if(i < 2 || f[i] > f[i - 1])
                T.clear(T.rt[0]), T.rt[0] = T.rt[1], T.rt[1] = 0;
            g = T.query(T.rt[0], a[i], 29, 0);
            if(i >= last && i < n && f[i] == f[n] - 1 && g <= a[i + 1])
                ans = f[n] - 1;
        }
        cout << ans << '\n', T.clear(T.rt[0]), T.clear(T.rt[1]);
    }
    return 0;
}