Solution. ACC NOI 269D 谁

Description

有 $n$ 个数 $a_{1\dots n}$，每个数有一个颜色 $c_i$。

$m$ 次操作，每次操作修改一个数的颜色，并询问两个颜色不同的数的最小异或和。

$1\le n,m\le2\times10^5,1\le c_i\le n, 0\le a_i<2^{30}$

保证 $a_i$ 单调不降。

Solution

异或会让人想到线性基和 01-trie，既然是两个数的异或和，那就跟线性基没什么关系了。

这个题可以直接在 01-trie 上维护。我们维护每个子树内是否都是同种颜色，如果不是则维护子树内的最小异或和，合并的时候可以直接继承一边子树的信息。如果两边子树都标记为有颜色且颜色不同，那么意味着选取的两个数应该一个来自左子树一个来自右子树，这样得到的最小异或和可以在最开始的时候 $O(n\log a_i)$ 用 dfs 预处理出来。不难发现接下来每次修改都是 $O(\log a_i)$ 的，于是总复杂度为 $O((n+m)\log a_1)$。

当然这样做维护的信息比较复杂，实现细节很多，我们还有一种比较直接且巧妙的做法。

我们构造一张 $n$ 个点的无向完全图，$u,v$ 之间的边权为 $a_u\oplus a_v$，查询最小异或和等价于查询最小边权。

题目要求两点颜色不同，我们发现，对于图中的一个环，找到环上边权最大的边，如果两个端点同色，则该边对答案无贡献，如果异色那么环上一定还有两端点异色且边权更小的边。所以答案一定在原图的最小生成树上。

然后这一部分就被转化为了经典题 Xor-MST，做法就是用 Boruvka，在 01-trie 上每到一个结点就合并两棵子树。

建出最小生成树后，观察在 01-trie 上建树的过程，不难发现一个点的度数最多是 $\log a_i$，所以我们可以用一个 multiset 维护树上所有合法的边权，每次修改时暴力更新与该点相邻的边，假设 $n,m$ 同阶，总复杂度为 $O(n\log n\log a_i)$。

Code

namespace Main{
    const int N = 200005;
    const int M = 3000005;
    int n, m, a[N], c[N];
    int ch[M][2], l[M], r[M], tot;
    vector<int> g[N];
    multiset<int> ans;
    void insert(int x, int id){
        int p = 0;
        for(int i = 29; i >= 0; i--){
            if(!ch[p][x>>i&1]) ch[p][x>>i&1] = ++tot;
            p = ch[p][x>>i&1];
            if(!l[p]) l[p] = id;
            r[p] = id;
        }
    }
    pair<int, int> operator + (pair<int, int> a, pair<int, int> b){
        return make_pair(a.first + b.first, a.second + b.second);
    }
    pair<int, int> query(int p, int x, int dep){
        if(dep == -1) return {l[p], 0};
        if(ch[p][x>>dep&1]) return query(ch[p][x>>dep&1], x, dep - 1);
        else return query(ch[p][~x>>dep&1], x, dep - 1) + make_pair(0, (1 << dep));
    }
    void dfs(int p, int dep){
        if(dep == -1) return;
        if(ch[p][0] && ch[p][1]){
            int mn = 1 << 30;
            pair<int, int> amn;
            for(int i = l[ch[p][0]]; i <= r[ch[p][0]]; i++){
                pair<int, int> tmp = query(ch[p][1], a[i], dep - 1);
                if(tmp.second < mn){
                    mn = tmp.second;
                    amn = {i, tmp.first};
                }
            }
            g[amn.first].push_back(amn.second);
            g[amn.second].push_back(amn.first);
        }
        if(ch[p][0]) dfs(ch[p][0], dep - 1);
        if(ch[p][1]) dfs(ch[p][1], dep - 1);
    }
    void Main(){
        input(n, m);
        for(int i = 1; i <= n; i++){
            input(a[i]);
            insert(a[i], i);
        }
        for(int i = 2; i <= n; i++){
            if(a[i-1] == a[i]){
                g[i-1].push_back(i);
                g[i].push_back(i - 1);
            }
        }
        for(int i = 1; i <= n; i++) input(c[i]);
        dfs(0, 29);
        for(int i = 1; i <= n; i++){
            for(int x: g[i]) if(x > i && c[i] != c[x]) ans.insert(a[i] ^ a[x]);
        }
        while(m--){
            int x, y;
            input(x, y);
            for(int t: g[x]) if(c[x] == c[t]) ans.insert(a[x] ^ a[t]);
            c[x] = y;
            for(int t: g[x]) if(c[x] == c[t]) ans.erase(ans.lower_bound(a[x] ^ a[t]));
            write(*ans.begin()), puts("");
        }
        return;
    }
} // namespace

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog

Solution. ACC NOI 269D 谁

Description

Solution

Code