湖南seo推广,南通网站优化找哪家,做外贸比较好用的网站有哪些,html做静态网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn序列aaa#xff0c;每两个点之间的边权为ai⊕aja_i\oplus a_jai⊕aj#xff0c;问你最小生成树的权值是多少。 n≤2e5,ai230n\le2e5,a_i 2^{30}n≤2e5,ai230
思路思路题意
给你一个长度为nnn序列aaa每两个点之间的边权为ai⊕aja_i\oplus a_jai⊕aj问你最小生成树的权值是多少。
n≤2e5,ai230n\le2e5,a_i 2^{30}n≤2e5,ai230
思路
看到最小生成树我们可以想到克鲁斯卡尔算法但是完全图显然不能直接做但是异或的话显然我们需要放到tiretiretire树上来跑的。
这里先介绍一种基于tiretiretire树分治的算法。
根据克鲁斯卡尔的思想我们需要找当前边权最小的点来合并显然就是两个点的lcalcalca中深度最深的位置但是这个比较难搞啊既然我们都放在tiretiretire树上了为什么不利用一下tiretiretire树的性质呢
根据tiretiretire树我们可知每个点最多有两个儿子并且可以拆位来看贡献
所以我们遍历tiretiretire树找每个可能为lcalcalca的点找一个最小的边加上当前位的贡献即可。
一个小技巧我们可以将aaa排序后依次插入那么tiretiretire每个点的区间都是连续的。
复杂度O(nlog2n)O(nlog^2n)O(nlog2n)
在考虑利用BoruvkaBoruvkaBoruvka算法来解决。
我们需要使用BoruvkaBoruvkaBoruvka算法来快速找出对于每个连通块与他连边最小的联通块是哪个让后不断折半最多进行lognlognlogn次。
考虑对每一个点aia_iai建一颗字典树让后对全局建一颗字典树比如要查与iii这个连通块异或值最小的联通块我们可以利用全局的tirealltire_{all}tireall减去当前的tireitire_{i}tirei这样就得到了其他连通块的tiretiretire在上面贪心的找即可合并的时候启发式合并即可。
不知道为何aaa排序就过了不排序过不了。
复杂度O(nlog2n∗α)O(nlog^2n*\alpha)O(nlog2n∗α)
// Problem: G. Xor-MST
// Contest: Codeforces - Educational Codeforces Round 32
// URL: https://codeforces.com/contest/888/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N200010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
LL a[N];
int tr[N*32][2],idx;
int l[N*32],r[N*32];void insert(int x,int id) {int p0;for(int i30;i0;i--) {int uxi1;if(!tr[p][u]) tr[p][u]idx;if(!l[p]) l[p]id; r[p]id;ptr[p][u];}if(!l[p]) l[p]id; r[p]id;
}LL query(int x,int p,int dep) {if(dep-1) return 0;int uxdep1;if(tr[p][u]) return query(x,tr[p][u],dep-1);else return query(x,tr[p][!u],dep-1)(1dep);
}LL dfs(int p,int dep) {if(dep-1) return 0;if(tr[p][0]tr[p][1]) {LL ans1e12;for(int il[tr[p][0]];ir[tr[p][0]];i) {ansmin(ans,query(a[i],tr[p][1],dep-1));}return dfs(tr[p][0],dep-1)dfs(tr[p][1],dep-1)ans(1dep);} else if(tr[p][1]) {return dfs(tr[p][1],dep-1);} else if(tr[p][0]) {return dfs(tr[p][0],dep-1);}return 0;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in;i) scanf(%d,a[i]);sort(a1,a1n);for(int i1;in;i) insert(a[i],i);printf(%lld\n,dfs(0,30));return 0;
}
/**/
// Problem: G. Xor-MST
// Contest: Codeforces - Educational Codeforces Round 32
// URL: https://codeforces.com/contest/888/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairLL,LL PII;const int N300010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
LL a[N];
int tr[N*50][2],root[N],idx,cnt[N*50],ed[N*50];
int p[N],se[N],id[N];
LL d[N];int find(int x) {return xp[x]? x:p[x]find(p[x]);
}void dfs(int p,int q) {cnt[p]cnt[q];ed[p]ed[q];for(int i0;i2;i) {if(tr[q][i]) {if(!tr[p][i]) {tr[p][i]tr[q][i];} else dfs(tr[p][i],tr[q][i]);}}
}void merge(int a,int b) {int pafind(a),pbfind(b);if(papb) return;if(se[pa]se[pb]) dfs(root[pb],root[pa]),p[pa]pb,se[pb]se[pa];else dfs(root[pa],root[pb]),p[pb]pa,se[pa]se[pb];
}void insert(int p,int x,int id) {ed[p]id;for(int i30;i0;i--) {int uxi1;if(!tr[p][u]) tr[p][u]idx;assert(idxN*50);ptr[p][u]; cnt[p];ed[p]id;}
}PII query(int x,int p) {int pproot[0];LL ans0;for(int i30;i0;i--) {int uxi1;if(tr[pp][u]cnt[tr[pp][u]]-cnt[tr[p][u]]0) ptr[p][u],pptr[pp][u];else ptr[p][!u],pptr[pp][!u],ans1i;}return {ed[pp],ans};
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in;i) scanf(%lld,a[i]);random_shuffle(a1,a1n);root[0]idx;for(int i1;in;i) {root[i]idx; p[i]i; se[i]1;assert(idxN*50);insert(root[i],a[i],i); insert(root[0],a[i],i);}// merge(3,2); merge(1,3);// PII nowquery(a[3],root[find(3)]);// coutnow.X now.Yendl;// return 0;LL ans0;int all0;while(1) {for(int i1;in;i) d[i](1ll31)-1;int cur0;for(int i1;in;i) {PII nowquery(a[i],root[find(i)]);int xfind(i),yfind(now.X);if(xy) continue;if(d[x]now.Y) d[x]now.Y,id[x]now.X;if(d[y]now.Y) d[y]now.Y,id[y]x;}for(int i1;in;i) if(d[i]!(1ll31)-1find(i)!find(id[i])) {merge(i,id[i]); ansd[i];cur;}if(!cur) break;}coutansendl;return 0;
}
/**/
