牛客周赛Round67A~F题解目录牛客周赛Round67A~F题解Preface所有代码前面的火车头ProblemA.排序危机ProblemB.小歪商店故事：卷ProblemC.小苯的计算式ProblemD.KProblemE.小苯的区间选数ProblemF.小Z的树迁移PostScriptPreface好久没v过牛客周赛了，但估计这场强度不高

OIWIKI何为DSUonTree其实是一个CF算法标签即为树上启发式合并，既然为启发式合并，必然会有一些人类智慧的存在（相当于卡常）。DSUonTreeStep1.找出重儿子这里就是重链剖分中的定义就行了。Step2.暴力对于所有的儿子，我们直接先按照题意暴力一遍。对于所有的轻儿子，我

大体思想线段树分治是一种用于解决区间操作和时间点查询的算法。它的主要思想是以时间为下标建立线段树，将在某一时间段内生效的操作记录在线段树上，然后对于某一时间点的查询，可以直接从线段树上得到结果。线段树是一种容易维护区间的数据结构，它通过不断以中点分治区间，形成了\(log

轩辕4721年，彩笔@硒六爱吃硫，在某日的西艾斯批%你赛中花了两个小时切掉了T1和T2。随后看到T3，心想：“这不是傻逼题吗，建下克鲁斯卡尔重构树然后瞎几把低批不就做完了吗。”发现并不会低批。思考了一个小时发现并不是沙比低批，而是地艾斯优盎吹。@硒六爱吃硫打完暴力。注意到

题意输入一个正整数\(T(1\leqT\leq10^4)\)，表示接下来输入\(T\)组测试用例，对于每一个测试用例：第一行，输入一个正整数\(n(2\leqn\leq2*10^5)\)第二行，输入\(n\)个正整数\(a_i(1\leqa_i\leqn)\)，表示节点\(i\)到节点\(a_i\)存在一条有向边，保证无自环这\(n

版本1：路径压缩。structDSU{ std::vector<int>fa; voidinit(intn){ fa.resize(n+1); std::iota(fa.begin(),fa.end(),0); } intleader(intx){ while(x!=fa[x]){ fa[x]=leader(fa[x]); } returnfa[x]; } voidjoin(intx,inty){ x

可能做到好题之后会再更新吧。总叙线段树与离线询问结合技巧又被称为线段树分治。使用线段树分治维护的信息通常会在某一个时间段内出现，要求在离线的前提下回答某一个时刻的信息并，则可以考虑使用线段树分治的技巧。以下是线段树分治的基本模板：change将信息按时间段覆盖在线

只能基础查询到根节点的距离structDSU{intfa[N],siz[N],deep[N];voidinit(){for(inti=1;i<=n;i++){fa[i]=i;siz[i]=1;deep[i]=0;}}intfind(intx){inttmpfa=fa[x];

0829-T4太空帝国题意给定一个图有\(n\)个点，每个点的坐标为\((x_i,y_i,z_i)\)。点\(i\)和点\(j\)的距离为\(\min(|x_i-x_j|,|y_i-y_j|,|z_i-z_j|)\)。求该图的最小生成树。思路暴力建图不能通过。对最小生成树有贡献的边只可能连在按\(x\)或\(y\)或\(z\)排序

P9992[YnoiEasyRound2024]TEST_130之前大概想出来了，但是没想清楚。发现每次询问\(w,d\)就相当于算\(w\)子树里离\(w\)距离不超过\(d\)的点的贡献之和，\(w\)的贡献是\(d+1\)（因为\(N(w,0),N(w,1),\ldots,N(w,d)\)都可以），\(w\)往下第一层的每个点分别的贡

参考文章：树上启发式合并[dsuontree]树上启发式合并总结树上启发式合并の详解启发式合并启发式算法是什么呢？启发式算法是基于人类的经验和直观感觉，对一些算法的优化。举个例子，最常见的就是并查集的启发式合并了，代码是这样的：voidmerge(intx,inty){intxx=find(x

【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)

树分治这部分知识是我的弱项，之前学习时也没有听懂。此前碰到这类题也会想尽办法用数据结构代替，但发现非常不可做，代码复杂程度极高。而且感觉之前我连普通的区间分治都不太熟练，没有学好的信心。现在学习过后好了很多，理解了分治的核心（也许），就是每次到分治的关键点就去统计包含关键点

关于迟到这么多天就迟到一次就被抓了个正着/jk今天刚好错过地铁，后来在地铁上碰见了int08，本来他和我都坐的上一班结果今天都迟到了，然后在路上就一直讨论李老和hfu抓住我们的概率。本来我想今天迟到就算了，毕竟刚好错过地铁下一班要等好一会没办法，但int08认为他有很大概率被抓

StampRallykruskal重构树板子，套上二分求一下祖先即可。AND-MEXWalk注意到答案只可能是0,1,2。因为1和2显然不能同时存在。证明：可知边权序列不增，如果前面出现2则说明第1位是0，由于是与运算所以不可能有1了。判断0和1即可。0好判断，只要全不为0，也就是最后

关于冰茶姬简述冰茶姬是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，冰茶姬支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于

前置知识:树链剖分的一些东西会打暴力DSUOnTree是啥中文名:树上启发式合并/静态链分治先考虑启发式合并是啥:说到启发式合并，那么常见的就是并查集了。我们将小的集合合并到大的集合中，就可以变成\(O(n\logn)\)神奇让高度小的树成为高度较大的树的子树，这个优化可

dsuontree模板运用例题以及代码：U41492树上数颜色-洛谷|计算机科学教育新生态(luogu.com.cn)记录详情-洛谷|计算机科学教育新生态(luogu.com.cn)Lomsatgelral-洛谷|计算机科学教育新生态(luogu.com.cn)记录详情-洛谷|计算机科学教育新生态(luogu.com.

CL-21一般拿到这个题第一眼都应该能看出并查集，subtask1是给并查集暴力修改的.后面subtask2没有联通操作，是给纯线段树的，也算是启发正解了再往下可以考虑操作\(1\)采用线段树区间修改，操作\(2\)采用并查集维护的思路.按这个思路去想，那么操作\(2\)肯定不能进行修改，因为我

数据结构——并查集学习笔记并查集是一种用于管理元素所属集合的数据结构，实现为一个森林。并查集中，每棵树表示一个集合，树中的节点表示对应集合中的元素。其思想是，把集合属性绑定到根节点上，避免多余的处理，因此一般难以分离。普通并查集并查集支持两种操作：合并（Union）：合并两个元素

给定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的美妙性质，让他求解这个问题！然