Xor-MST 更优秀的做法

· · 题解

Xor-MST 更优秀的做法。

转换部分略过，重点讲优化。转换后，对于 trie 上的每一个节点，你需要求出它左右子树中异或的最小值。

目前有两种做法，一种是把一棵子树内所有数插入另一棵子树，另一种是两棵子树同时遍历，能同侧递归就同侧递归，否则异侧递归，这种做法不把 trie 建出来也行。

分析一下复杂度，由于树高是 O(\log a) 的，每个节点最多被遍历 O(\log a) 次。第一种做法还可以用启发式合并优化到 O(\log n) 次。又因为总结点数是 O(n\log v) 的，所以总时间复杂度是 O(n\log^2a) 或 O(n\log a\log n)，是能卡满的。

看上去就很能优化。

注意到，trie 上有用的节点只有 O(n) 个，具体地说，只保留 trie 上有两个儿子的节点和叶子就能发挥相同的作用，建 trie 的虚树就行。就完了。时间复杂度 O(n\log v)。

实现上，每个节点需要存下它的深度和它代表的从根到这个节点的路径（用一个数表示）。往下跳时直接选一个儿子跳，每次会跳过一段。

先放一份实现得很史的代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int NN=500000,L=30,K=2,INF=2000000000;
int d[NN],vv[NN][K],trans[NN][K],b[L+1],vvv[NN],mi,pp[NN];
long long ans;
bool ss;
int work(int l,int r)
{
    return b[r-l]<<l+1;
}
void init(int p)
{
    if (trans[p][0])
    {
        vv[p][0]&=work(d[trans[p][0]],d[p]);
        vvv[trans[p][0]]=vvv[p]^vv[p][0];
        init(trans[p][0]);
    }
    if (trans[p][1])
    {
        vv[p][1]&=work(d[trans[p][1]],d[p]);
        vvv[trans[p][1]]=vvv[p]^vv[p][1];
        init(trans[p][1]);
    }
}
void dfs(int p)
{
    int ppp,to,p1,p2;
    bool k;
    ppp=pp[p];
    if (d[ppp]>-1)
    {
        k=vvv[p]>>d[ppp]&1;
        while (1)
        {
            to=trans[ppp][k];
            if (!to||d[to]<d[p]) break;
            ppp=to;
            if (d[ppp]>d[p]) k=vvv[p]>>d[ppp]&1;
        }
    }
    if (d[p]>-1)
    {
        p1=trans[p][0];
        pp[p1]=ppp;
        dfs(p1);
        p2=trans[p][1];
        pp[p2]=ppp;
        dfs(p2);
    }
    else mi=min(mi,vvv[p]^vvv[ppp]);
}
void trie(int p)
{
    if (trans[p][0]) trie(trans[p][0]);
    if (trans[p][1]) trie(trans[p][1]);
    if (trans[p][0]&&trans[p][1])
    {
        mi=INF;
        pp[trans[p][0]]=trans[p][1];
        dfs(trans[p][0]);
        ans+=mi;
    }
}
int main()
{
    int n,tot,i,a,j,p,v;
    bool k;
    scanf("%d",&n);
    ss=n==800;
    d[0]=L-1;
    tot=1;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a);
        p=0;
        for (j=L-1;j>-1;j--)
        {
            if (d[p]>j)
            {
                v=vv[p][k];
                if ((a>>j&1)!=(v>>j&1))
                {
                    d[tot]=j;
                    vv[tot][a>>j&1]=a;
                    vv[tot][v>>j&1]=v;
                    trans[tot][a>>j&1]=tot+1;
                    trans[tot][v>>j&1]=trans[p][k];
                    trans[p][k]=tot++;
                    d[tot++]=-1;
                    break;
                }
            }
            else
            {
                if (!trans[p][a>>j&1])
                {
                    d[tot]=-1;
                    vv[p][a>>j&1]=a;
                    trans[p][a>>j&1]=tot++;
                    break;
                }
                k=a>>j&1;
            }
            if (d[trans[p][k]]==j-1) p=trans[p][k];
        }
    }
    for (i=1;i<=L;i++) b[i]=(1<<i)-1;
    init(0);
    trie(0);
    printf("%lld",ans);
    return 0;
}

这份代码可读性低（我已经看不懂了），跑起来也不那么快。

简单解释一下，建 trie 时是暴力插入，init 函数是预处理节点信息的，后面的思路大概是上面讲的第一种，遍历左子树，对于其中每一个节点维护其对应的右子树中的节点，转移到儿子时在右子树暴力跳。

有没有更好的实现方法呢？

先看建树（和上面的代码没有任何关系）：

int build(int l,int r,int al,int ar,int deep)
{
    int mid,id,amid;
    if (l==r)
    {
        d[t]=deep;
        v[t]=a[al];
        return t++;
    }
    mid=l+r>>1;
    if (a[ar]<=mid) return build(l,mid,al,ar,deep-1);
    if (a[al]>mid) return build(mid+1,r,al,ar,deep-1);
    id=t++;
    d[id]=deep;
    amid=upper_bound(a+al,a+ar,mid)-a-1;
    e[id][0]=build(l,mid,al,amid,deep-1);
    e[id][1]=build(mid+1,r,amid+1,ar,deep-1);
    v[id]=v[e[id][0]];
    return id;
}

思想上类似于线段树或整体二分。

如果区间中的数集中在一侧就直接向一侧递归，否则二分出断开的位置。递归次数 O(n\log v)，二分次数 O(n)，时间复杂度 O(n(\log a+\log n))。

再看查询：

int work(int rt1,int rt2)
{
    int rt3,rt4;
    if (d[rt1]==-1&&d[rt2]==-1) return v[rt1]^v[rt2];
    if (d[rt1]==d[rt2]) return min(work(e[rt1][0],e[rt2][0]),work(e[rt1][1],e[rt2][1]));
    rt3=rt1;
    rt4=rt2;
    if (d[rt3]<d[rt4]) swap(rt3,rt4);
    return work(e[rt3][v[rt4]>>d[rt3]&1],rt4);
}

用的是上面讲的第二种，按深度简单分讨一下。

那么，结束了，上完整代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) putchar(x)
inline int read() {
  int x = 0, sgn = 0; char s = getc();
  while(!isdigit(s)) sgn |= s == '-', s = getc();
  while(isdigit(s)) x = x * 10 + s - '0', s = getc();
  return sgn ? -x : x;
}
inline void print(long long x) {if(x >= 10) print(x / 10); putc(x % 10 + '0');}
const int N=400000,V=1073741823,K=2,D=29;
int a[N],t,d[N],v[N],e[N][K];
int build(int l,int r,int al,int ar,int deep)
{
    int mid,id,amid;
    if (l==r)
    {
        d[t]=deep;
        v[t]=a[al];
        return t++;
    }
    mid=l+r>>1;
    if (a[ar]<=mid) return build(l,mid,al,ar,deep-1);
    if (a[al]>mid) return build(mid+1,r,al,ar,deep-1);
    id=t++;
    d[id]=deep;
    amid=upper_bound(a+al,a+ar,mid)-a-1;
    e[id][0]=build(l,mid,al,amid,deep-1);
    e[id][1]=build(mid+1,r,amid+1,ar,deep-1);
    v[id]=v[e[id][0]];
    return id;
}
int work(int rt1,int rt2)
{
    int rt3,rt4;
    if (d[rt1]==-1&&d[rt2]==-1) return v[rt1]^v[rt2];
    if (d[rt1]==d[rt2]) return min(work(e[rt1][0],e[rt2][0]),work(e[rt1][1],e[rt2][1]));
    rt3=rt1;
    rt4=rt2;
    if (d[rt3]<d[rt4]) swap(rt3,rt4);
    return work(e[rt3][v[rt4]>>d[rt3]&1],rt4);
}
int main()
{
    int n,i;
    long long ans;
    n=read();
    for (i=0;i<n;i++) a[i]=read();
    sort(a,a+n);
    build(0,V,0,n-1,D);
    ans=0;
    for (i=0;i<t;i++) if (d[i]>-1) ans+=work(e[i][0],e[i][1]);
    print(ans);
    return 0;
}

小清新很多，跑到 CF 第一页，略逊于卡常巨佬。

我与 Xor-MST 的故事。