一并查集尾声边带权并查集进阶题目推理查询一个数组a里面有2的30次方个整数下标为0到2的30次方−1。一开始你只知道每个数的范围是[0,2的30次方−1]但是并不知道每个数的具体数值。现在你要处理两种类型的操作1、1 l r x你被告知区间[l,r]内的元素异或和的结果是x即a[l]⊕a[l1]⊕…⊕a[r] x⊕为异或运算。如果当前给出的信息和前面的产生了矛盾应该忽略最新的这条信息。2、2 l r输出区间[l,r]内的元素异或和即输出a[l]⊕a[l1]⊕…⊕a[r]的结果。如果我们无法推出答案则输出-1。输出时强制在线第一行包含一个整数 q 表示操作的数量。接下来的q行每一行描述一个操作。每行的第一个数 t 表示操作的类型。给出的查询通过以下方式加密用 last 表示上一个 t2 类型询问对应的正确答案最初last0如果上一个答案为 -1则令 last1如果 t1 后面跟着三个整数L,R,X令l L⊕last, r R⊕last, x X⊕last如果l r的则交换l和r的值现在我们知道区间[l,r]内的元素异或和为x如果本次得到的信息和前面的产生了矛盾则忽略掉如果t2后面跟着两个整数 L,R令l L⊕last, r R⊕last如果 l r 的则交换 l 和 r 的值输出区间[l,r]内的元素异或和如果我们没法根据前面给出的信息推断出答案则输出-1。不要忘记每次执行完t2的操作之后更新last。输入保证t2的操作至少有一个。下标到2的30次方显然无法直接用数组来存我们考虑unordered_map存储重点在于查询询问区间和首先考虑前缀和思路若[L,R]完整存储 直接返回dis[R]^dis[L-1]若[L,R]可拆分为[L,x][x1,R] 返回dis[x]^dis[L-1]^dis[R]^dis[x]两次异或直接抵消变为dis[R]^dis[L-1]观察到似乎有一些图上连通性的感觉LR通过x祖先被链接在一起形成连通块若无法形成连通块就没有答案考虑并查集这样把问题转换成了区间[l, r]的异或和 点l-1和点r两点之间的异或距离。对于操作1等价于L-1注意到R链接了一条权值为k的边对于操作2则通过上述公式返回dis[R]^dis[L-1]我们分析一下dis[x]含义到底是什么x到祖先的异或距离dis[L]和dis[R]关系大概长这样L---------------------------x[我是答案]R-------------x是不是答案就有了那dis[x]咋求下文距离均代表异或距离在find函数中原本fa[x]就是x的祖先所以dis[x]就是x到fa[x]的距离后续的合并中fa[x]有了新的fa那么此时fa[x]不再是x的祖先成为旧祖先那么dis[fa[x]]就是旧祖先到新祖先的距离所以x到新祖先的距离就是x到fa[x]旧祖先的距离dis[x]和旧祖先到新祖先的距离那update呢 dis[xx]dis[x]^dis[y]^k;我是k-----------------------x---------xx y-----------yy------------- ---------------我是dis[x] 我是dis[y]------------------------- ----两个dis[x]重叠抵消了哦dis[x]^dis[y]^k很明显吧代码如下补充map.count(x)数x作为下标的数的个数#includebits/stdc.h #define ll long long using namespace std; const int N1e55; int T,n,m; unordered_mapint,int fa,dis; int Find(int x) { if(!fa.count(x)) { //x没出现过 return fa[x]x; } if(fa[x]x) return x; int fFind(fa[x]); dis[x]^dis[fa[x]]; return fa[x]f; } void Union(int x,int y,int k) { int xxFind(x),yyFind(y); if(xxyy) return ; fa[xx]yy; dis[xx]dis[x]^dis[y]^k; } int main() { scanf(%d,T); int last0; while(T--) { int opt,L,R; scanf(%d%d%d,opt,L,R); L^last,R^last; if(LR) swap(L,R); L--;//对L-1做操作 if(opt1) { int x; scanf(%d,x); x^last; Union(L,R,x); } else { if(Find(L)!Find(R)) { //不连通无答案 last1; printf(-1\n); } else { lastdis[L]^dis[R]; printf(%d\n,last); } } } }扩展域并查集只看一个题团伙现在有 n 个人他们之间有两种关系朋友和敌人。我们知道一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友现在要对这些人进行组团。两个人是朋友就在一个团伙中。请求出这些人中最多可能有的团体数。扩展域并查集每个点有多种状态状态之间做合并来判定关系一个人有朋友和敌人两种状态这个题中设i为i这个点的朋友态本体设in为i这个点的敌人态即若有i作为某某的敌人的场景此时的i变为in普通并查集只能维护同类关系无法同时处理「朋友 / 敌人」两类对立关系因此采用拆点 把每个人 i 拆成两个点i代表 i 的朋友域自己和朋友in代表 i 的敌人域敌对如果一个人和我的朋友态联通在我的朋友域那他就是我的朋友我俩是一伙的如果一个人和我的敌人态联通在我的敌人域那我俩就不是一伙的统计团伙数量时考虑本体所属的团体set去重记录团体数量#includebits/stdc.h using namespace std; const int N2e35; int n,m,ans,fa[N]; int Find(int x){ if(fa[x]x) return x; return fa[x]Find(fa[x]); } void Union(int x,int y){ int xxFind(x),yyFind(y); fa[xx]yy; } int main(){ scanf(%d%d,n,m); for(int i1;i2*n;i) fa[i]i; while(m--){ int x,y; char c[2]; scanf(%s%d%d,c,x,y); if(c[0]F) Union(x,y); else{ //x和y是敌人敌人的敌人是朋友 Union(yn,x);//y的敌人和x的朋友是一类 Union(xn,y);//x的敌人和y的朋友是一类 } } setint s; for(int i1;in;i){ s.insert(Find(i)); } printf(%d,s.size()); }二最小生成树kruskal算法什么是最小生成树把整张图所有点全部连起来不能有环一共 n 个点只用 n-1 条边。 简单说连通全部点、无环的子图 生成树。满足上面生成树的条件并且所有边的权值加起来总和最小就是最小生成树。那克鲁斯卡尔算法是把所有边按权从小到大排序从小到大依次拿边如果这条边的两个点不在同一集合连上不会成环就选这条边直到选出 n-1 条边结束。这样就有了最小生成树了总体是一个贪心的算法模板如下bool cmp(node x,node y){ return x.zy.z; } int Find(int x){ if(xfa[x]) return x; return fa[x]Find(fa[x]); } int kruskal(){ sort(edge1,edgem1,cmp); for(int i1;in;i){ fa[i]i; } int ans0,cnt0; for(int i1;im;i){ int xxFind(edge[i].x),yyFind(edge[i].y); if(xxyy) continue; cnt; ansedge[i].z; fa[xx]yy; } if(cnt!n-1){ return 0; } return ans; }今天就这样明天应该是有prim和例题还有最后3篇了
