给定N条直线、M组位置关系(平行或垂直)和Q个查询，要求输出共有多少组平行线，并回答询问的直线之间的位置关系。提示：种类并查集。#include<bits/stdc++.h>usingi64=longlong;structDSU{std::vector<int>f;DSU(intn){init(n);}voidinit(

E-CliqueConnecthttps://atcoder.jp/contests/abc352/tasks/abc352_e最小生成树先复习一下最小生成树，这里用Kruscal生成树（spanningtree）：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择\(n-1\)条，将所有顶点连通。最小生成（MinimumSpanningTree，MST）：边

从启发式合并到DsuonTree传统启发式合并[HNOI2009]梦幻布丁题目描述\(n\)个布丁摆成一行，进行\(m\)次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。例如，颜色分别为\(1,2,2,1\)的四个布丁一共有\(3\)段颜色.输入格式第一行是两

有人说，直接点分树，力大砖飞，非常不错！实际上这种做法非常的垃圾，很多时候我们使用点分树，一定是不得不使用点分树，比如模板题，强制在线，非常的恶心，所以我们使用点分树。而点分树是否必要呢？既然你能看到这篇blog，他肯定是不必要的！我们今天来发掘dsuontree的美妙性质，让他求解这个问题！然

VP的。猜猜为啥没有penalty？因为T的没有测完。submissionsA,B直接暴力。C一个很简单的方法就是第\(i\)次把\(i\)放到应该在的位置。当然如果原先就在了就别管。D一个联通图中的每两个点都能成为朋友。因此直接dsu。E记忆化搜索。注意到如果投骰子投到\(1\)，直接

主要思想是树的重轻儿子之分使得时间复杂度为o(nlogn),神奇欲深入了解的这里:https://oi-wiki.org/graph/dsu-on-tree/点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedefstructedge//边结构体{intto,next;}EDGE;//边相关数组EDGEe[100001<<1];

今天模拟赛T2用到了，所以来浅浅地学一下DSUontree。对于一类树上问题（大多是和路径有关的），其暴力复杂度通常会带上一个\(n^{2}\)，这时利用启发式合并就可以将其优化到\(n\logn\)。具体地，假设搜索到了\(u\)结点，令\(son_{u}\)表示结点\(u\)的重儿子，那么：先对\(u\)的

树上启发式合并适用于维护子树内信息例题：CF246E思路暴力将询问离线下来，挂在每个点上对于每个点\(x\)，维护一个桶\(cnt_{dep}\)，统计深度\(dep\)下不同字符串出现的次数对于\(x\)上的询问输出\(cnt_{dep_x+k}\)每切换一个\(x\)，\(cnt\)要重置\(DSU\)优化维护

在地铁上口胡了一下。不知道对不对。考虑记录每一个点\(i\)离他最远的一个祖先使得祖先到\(i\)的路径上没有\(a_i\)。设他为\(\text{lst}_i\)。然后如果两个\(u,v\)的\(\text{lst}\)相等，那么这条路径就是好的。每种颜色枚举即可。八成假了（？），欢迎Hack。PS：全对了，确实能

题意给定一棵树，求区间\([l,r]\)中任意两点的LCA的不同的带权深度的个数。Sol很容易想到Dsuontree。因为当前点\(x\)作为LCA产生贡献当且仅当有两点\(u,v\)分别在\(x\)的不同子树中。集中注意力，不难发现对于一个\(u\)来说，只有子树中她在序列上的前驱后继会

https://www.luogu.com.cn/problem/CF1702E转化题意把所有数连边，判断是否为二分图。染色法voidsolve(){#definetestsintn;std::cin>>n;std::map<int,std::vector<int>>edge;std::vector<bool>used(n+1);boolok(true);

线段树合并&DsuontreeCF600E线段树合并，每个节点下维护子树下每个颜色的数量，建立权值线段树复杂度证明：叶子节点\(O(logm)\)Dsuontree重儿子信息保留，轻儿子信息递归计算一次，合并一次。复杂度证明：对于一个点，最多经过\(O(\logn)\)条轻边，第一次被递归执行一次，每次被当

https://codeforces.com/problemset/problem/277/AItpresentsaproblemthatweneedtomakeallelementconnected,itcanbesolvedbyusingdsu.Ididn'tusemydsumodelandwriteasimpleversionofDsu.classDSU{public:DSU(intm):size_(m){

以一道区间和查询来说明板子如何使用1.merge的时候只需要维护两个根节点的距离，利用的是合并时题目给的信息2.find的时候更新维护是子节点到根的距离3.需要加一个查询函数，因为距离数组是开在结构体内部的。题目描述对于一个长度为\(N\)的整数数列\(A_{1},A_{2},\cdotsA_

目录问题引入算法原理参考代码问题引入给出n个人的m个关系，表示给出的两个人都是朋友关系，之后进行k次询问，要求判断给出的两人是否是朋友关系，朋友的朋友也是朋友算法原理简单来说就是对集合的合并进行一个处理，使得是朋友的一群人用一个共同的朋友记录，这样在查询的时候就可以通过

目录写在前面引入树上启发式合并代码复杂度分析例题CF570DTreeRequestsCF600ELomsatgelralCF1709EXORTree写在最后写在前面高产似那啥。还以为这东西是啥科技呃呃，原来是能证明复杂度的乱搞。所以重链剖分就是动态dsu（精神错乱引入dsuontree，即树上启发式合并。启发

dsuontree前言在我认为，这个并不能说单独列出来成为一个算法，更恰当的说，是一种思想、技巧。反正挺简单的，也很有趣（谁会拒绝一个优美的暴力呢），所以写篇笔记记录一手。dsu是什么dsu一般指“disjointsetunion”，即并查集。那么dsuontree也就是指树上的合并和查询操作。但是

91-B题目大意给定一个长为\(n\)的序列\(a\)，对于每个\(a[i]\)，你需要找到一个\(j\)满足\(a[i]>a[j]\)且\(j-i\)最大。Solution逆序遍历，维护一个单调递减的栈，如果当前枚举的\(a[i]\)小于栈顶元素，则入栈。如果\(a[i]\)大于栈顶元素，那么后面的元素如果大于\(a[i]\)，那么也大于栈顶

292-D题目大意给定一张无向图，由\(n\)个顶点\(m\)条边。有\(q\)次询问，每次询问将\([l,r]\)的边删去，问图中有多少连通分量。Solution涉及连通分量，尝试应用并查集解决。记录一个前缀并查集\(pre[i]\)，表示前\(i\)条边连通后的图；和一个后缀并查集\(suf[i]\)，表示后\(m-i\)条边连通

dsuonTree(树上启发式合并)当遇到处理子树询问，并且无修改时。可以考虑树上启发式合并。算法流程：step1：处理出每个点的\(siz_x\)以及重儿子\(son_x\)。voiddfs(intx,intfa){ siz[x]=1; intMaxson=0; for(inti=0;i<p[x].size();i++){ inty=p[x]

structDSU{vector<int>f,siz;DSU(){}DSU(intn){init(n);}voidinit(intn){f.resize(n);std::iota(f.begin(),f.end(),0);siz.assign(n,1);}intfind(intx){

树上启发式合并（dsuontree）通常用来查询不带修的子树信息，信息要求可合并。对于一个结点\(u\)，其步骤如下：求解其轻儿子的答案，同时清除递归产生的影响。求解其重儿子的答案，保留递归产生的影响。将轻儿子子树内的每个结点都合并进答案中，同时成为以\(u\)为根的子树产生的影响。

题如其名，确实挺经典的。我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。显然，对于连续的若干平凡点\([l,r]\)，他们内部的最优连边方式就是连成一条链，花费\(r-l\)的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成

[POI2003]Monkeys题解正着做貌似不好做，发现猴子是否掉落取决于“最后一根稻草”，也就是最后撒手的那个猴子，那我们考虑倒着把猴子网拼回去。这样，每群猴子掉落的时刻就是与\(1\)号猴子连通的时刻。利用并查集可以维护猴子的连通性，但是怎么更新答案呢？这里用vector进行了一个猴

[JOISC2014]電圧题解赛时都想到了我也不知道为啥自己没敢写首先题意可以转化为，我们去掉一个边后，剩下的图可以黑白染色，同时保证去掉的边两端的点颜色相同，问这样的边数。换句话说，去掉一条边后，剩下的图应该是一个二分图。然后我们很容易想到线段树分治来处理这种问题。每次只有