CodeForces 888G Xor-MST（Sollin MST+Trie）

G. Xor-MST

time limit per test：2 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

n vertices. A number ai is assigned to each vertex, and the weight of an edge between vertices i and j is equal to ai xor aj.

Calculate the weight of the minimum spanning tree in this graph.

Input

n (1 ≤ n ≤ 200000) — the number of vertices in the graph.

n integers a1, a2, ..., an (0 ≤ ai < 230) — the numbers assigned to the vertices.

Output

Print one number — the weight of the minimum spanning tree in the graph.

Examples

Input

5
1 2 3 4 5      

Output

8      

Input

4
1 2 3 4      

Output

8      

           标題都已經很明顯了，一個最小生成樹，隻不過是用xor做。

        通常來說xor的題目，要麼是貪心，要麼是用Trie去做，而這道題，顯然要用到Trie。但是我們又如何做到求最小生成樹呢？這裡，我們發現求最小生成樹有一個非常少見的算法——Sollin(Boruvka)算法。具體來說，就是一開始把每個點看成獨立的連通分量，對于每個連通分量，每次操作找與其最近的連通分量合并，一直到隻剩下一個連通分量為止。這樣子最壞的情況是每次隻減少一半的連通分量數目，最好的情況就直接和Prim算法相同。具體實作起來，可能不太友善，而且實踐複雜度看起來不小（要枚舉連通分量，以及其中的各個點，還要求最小）。

       然後，對于本題，相當于是一個模闆題。由于是用xor求最小值，是以我們可以用Trie來優化求最近的連通分量的過程。對于每一個集合，我們用并查集來維護合并的過程。具體執行起來，如果用vector去存各個連通分量裡面的數字，據說可能會超内促成你，是以用了排序的方法。對于每個數字，我們按照他所在的連通分量排序，這樣同一個連通分量的點就在同一個連續區間裡面，然後每次把一個連通分量所有點先從Trie中删去，然後再周遊連通分量所有的點，對于每個點在剩下的Trie中找最小，最小之中的最小即為解，然後合并即可。這裡注意連通分量A與B合并之後，在這一次操作中就不需要再用B來與其他連通分量合并。

        具體見代碼：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define N 200010

using namespace std;

struct Trie
{
    struct node{int size,ch[2];} T[N<<5];
    int tot,root;

    void init()
    {
        tot=root=1;
        memset(T,0,sizeof(T));
    }

    void ins(int x)
    {
        int o=root;
        T[o].size++;
        for(int k=30;k>=0;k--)
        {
            int c=x&(1<<k)?1:0;
            if(!T[o].ch[c]) T[o].ch[c]=++tot;
            o=T[o].ch[c];
            T[o].size++;
        }
    }

    void del(int x)
    {
        int o=root;
        T[o].size--;
        for(int k=30;k>=0;k--)
        {
            int c=x&(1<<k)?1:0;
            o=T[o].ch[c];
            T[o].size--;
        }
    }

    int query(int x)
    {
        int o=root,res=0;
        for(int k=30;k>=0;k--)
        {
            res<<=1;
            int c=x&(1<<k)?1:0;
            if (T[o].ch[c]&&T[T[o].ch[c]].size) o=T[o].ch[c],res+=c;
                                    else o=T[o].ch[c^1],res+=c^1;
        }
        return res;
    }
} Trie;

struct node{int fa,id;} p[N];
int f[N],w[N],n; LL ans;
bool v[N];

int find(int x)
{
    return f[x]==x ? x:(f[x]=find(f[x]));
}

bool cmp(node a,node b)
{
    return a.fa<b.fa;
}

bool check()                                                        //所有的點合并成同一個連通分量才算是合并完成
{
    for(int i=1;i<n;i++)
        if (find(i)!=find(i+1)) return 0;
    return 1;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    sort(w+1,w+1+n);
    n=unique(w+1,w+1+n)-w-1;
    for(int i=1;i<=n;i++)
    {
        p[i]=node{i,i};
        Trie.ins(w[i]); f[i]=i;
    }
    while(!check())
    {
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)
            p[i].fa=find(p[i].id);
        sort(p+1,p+1+n,cmp);                                        //按照所在連通分量編号排序
        int last=1,fa=p[1].fa;
        for(int i=1;i<=n;i++)
        {
            if (!v[fa]&&p[i].fa==fa) Trie.del(w[p[i].id]);            //删除具體的一個連通分量的所有點
            if (!v[fa]&&p[i+1].fa!=fa)                                    //删除完畢之後找其中最小的最小
            {
                v[fa]=1;
                int res=INF,k=0;
                for(int j=last;j<=i;j++)
                {
                    int tmp=Trie.query(w[p[j].id]);
                    if ((tmp^w[p[j].id])<res) res=tmp^w[p[j].id],k=tmp;
                }
                ans+=res;
                int pos=lower_bound(w+1,w+1+n,k)-w;
                if (fa>(pos=find(pos))) swap(fa,pos);
                for(int j=last;j<=i;j++)                                //把删掉的點重新加回Trie中去
                    Trie.ins(w[p[j].id]);
                f[find(pos)]=fa;                                            //合并
            }
            if (p[i+1].fa!=fa) fa=find(p[i+1].fa),last=i+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}