Posts match “ 并查集 ” tag:

并查集可以加入统计量,来统计某个等价类的性质。并且,通过在合并时更新,可以保留此类性质。

差统计量 维护的是两个节点之间差的统计量。有人将此类归作种类并查集,但其本质上维护的是两个节点之间差的值,并且通过合并来逐步完善差的关系。

进一步的解释:如果若干个元素在同一个集合中(从fa[x]可以观察出来),那么这个集合中任意两个元素x,y的差值rk[y]-rk[x]是一定的。
如果询问:所给的两个元素是否在同一个集合中/求两个元素的差值/求某一统计量,其可以间接转化为两个元素的差值/...,我们就可以通过判断rk[y]-rk[x]是否与询问一致/返回rk[y]-rk[x]的值来解决。

分析如下例子:
HDU 3038 How Many Answers Are Wrong
大致思路:这题就相当于判断两个元素的差统计量是否与所给的值矛盾,很明显,若两区间端点相邻或重合,我们就可以求出这些子区间及子区间合并后的区间的元素和。我们可以将区间变为左闭右开的形式(即区间右端点+1),然后合并两端点。
直接看样例:
一开始初始化所有rk[i]为0,并在接下来的合并x,y中保持fa[y]->fa[x](固定合并方向)
1 10 100 -> 合并1,11,rk[1]=0,rk[11]=100
7 10 28 -> 合并7,11,相当于合并7,1,求相对值后rk[1]=-72,rk[7]=0,rk[11]=28
1 3 32 -> 合并1,4,相当于合并7,4,求相对值后rk[4]=-40,其余不变
4 6 41 -> 发现4,7在同一个集合中,但rk[7]-rk[4]=0-(-40)=40,矛盾
6 6 1 -> 合并6,7,rk[7]=1,更新各节点之后rk[1]=-71,rk[4]=-39,rk[6]=0,rk[7]=1,rk[11]=29

继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=509&page=show_problem&problem=4225

思路:离线+逆序操作。逆序后删边变连边,用并查集判连通性即可。Q操作用名次树解决,C操作拆为删除和插入两个操作。
顺便附上我的Treap+名次树模板。

继续阅读

http://codeforces.com/contest/438

A题
考虑删除点的顺序,从点的大的往小的删除,然后考虑边的删除,我们会发现每条边对结果的“贡献”都是

B题
采用“边建图边计算”的方式。
依旧以边为主,首先对边按照min(a[u], a[v])递减排序,然后按此顺序加边,即用并查集动态维护连通分量。
由于边是按照min(a[u], a[v])递减排序的,所以两个连通分量上之间的连线所产生的“贡献”必为min(a[u], a[v]) * num[find(u)] * num[find(v)](根据乘法原理,以及这条边是桥),连通分量内的连线不产生贡献(因为不会经过)。

D题
如何处理操作2?
注意到若m<=a,则a%=m使a至少削减一半,所以这题维护区间和值以及区间最值,暴力完成操作2即可AC。

http://codeforces.com/gym/100463

切了场GYM。

A题
简单树状数组。

C题
首先对每个点连出的边进行极角排序(范围内),由于题意是逆时针旋转,我们可以G[i][angle[j].y] = angle[j + 1].y;这样用邻接矩阵建图。
建好图后 DFS 下就可以求出所有圈的长度了。

(顺便吐槽下此题时限为 40 s)

D题
直接枚举红点一半的组合就行,不需要判断是否有其他红点在所选的红点围成的矩形内,因为在这种情况下,一定有比该矩形更小的矩形。

E题
并查集。合并的时候要讨论清楚:

  1. 当 x==y 时集合唯一确定,用一个布尔数组 uni 表示(uni 表示 unique);
  2. merge 时要合并人数,集合大小,uni 这三个。

I题
这题需要有特殊的 YY 技巧。
由于要使A集合与B集合扩张成一个对减法封闭的,所以必须要有单位元 1 和 -1,进一步分析发现我们要判断出是否可以从A集合中可重复地取出 x 个数,从B集合中可重复地取出 x-1 或 x 个数,使得对于某些取法 sumA-sumB=1,某些取法 sumA-sumB=-1。

显然答案与有关,设其值为g,则 g=1 时可以扩张成;由于还可以先往右边多走一步,则 g=2 且集合A中存在奇数时也可以扩张成(g=2 说明可以扩展成偶整数集合,此时只要集合A中有个奇数就可以扩张成);但是对于 g>2 的情况却不行,这是因为此时扩张成 {...,-2g,-g,0,g,2g,...} 的集合,但又由于,所以,令,则只能扩张成形如 mg+k 的集合。
优化:

  1. 可以简化为
  2. 根据此简化式,判断集合A中是否有奇数可以简化为判断是否为奇数;
  3. 判断

附代码:

继续阅读