[Splay+并查集]AGM 2020 Qualification Round【Unpredictable Tree】题解
题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$ ，就可以方便的维护出DFS序。套...
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不...
[并查集按秩合并]Codeforces1444C【Team-Building】题解
题目概述CF1444C解题报告首先我们对于每个相同颜色的块，求出是否存在奇环，如果存在那么这种颜色显然不能选。排除了不能选的颜色之后，我们发现只有有边相连的两种颜色才有可能违法，因此会违法的颜色...
[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解
题目概述有 $m$ 条边，每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过，如果人数 $x$ 能够从 $1$ 到 $n$ 则可行，求可行的 $x$ 的数量。解题...
[并查集]洛谷6786【GCDs & LCMs】题解
题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ，然后推式子：$$
BA+CA+A={BA\cdot CA\over A}\\
BA+C...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的，所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并，考虑用set维护一个块的最大值，并查集合并的时候set启...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $l...
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径，每条路径节点个数不能超过 $L$ ，节点权值和不能超过 $S$ ，问最少分成多少路径。解题报告一个不知道正确性的解法，大佬可以来证明或者证伪一...
[思维+并查集]Codeforces1013D【Chemical table】题解
题目概述如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(r_2,c_2)$ 。现在 $n\...
[转化+并查集]Codeforces1027F【Session in BSU】题解
题目概述有 $n$ 场考试，第 $i$ 场考试可以在 $a_i,b_i$ 两天中的一天完成，问至少什么时候能考完所有试，无解输出 $-1$ 。解题报告我图样图森破，以为是神仙贪心，结果是转化思维...
