P4169-CDQ分治/K-D tree（三维偏序）-天使玩偶 这是一篇两种做法都有的题解 题外话 我写吐了…… 本着不看题解的原则，没写（不会）K-D tree，就写了个cdq分治的做法。下面是我的写题步骤： 想着树状数组维护不了区间最值，于是写了线段树，因为一个**的错误调了几个小时； cdq只写了两个方向。显然是错的，因为没考虑修改。所以挂了； 加上另外两个方向，...

P5311 [Ynoi2011] 成都七中 题意 给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。 查询操作给定参数 \(l\ r\ x\)，需输出： 将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。 每次查询操作独立。 思路 考虑点分树的思想。假设我们已经建出点分树，对于每一个分治中心，我们应该...

主定理（Master Theorem）通常是指在算法分析领域中的一个定理，特别是用于分析递归算法的时间复杂度。 时间复杂度相关定义 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。其原理在于，将计算机的每种基本运算（如加减乘除）所需的时间视为常数，然后考察一个算法调用了多大量级的基本运算。时间复杂度常用大 \(O\) 符号...

算法描述 运用了分治的思想，将一个数组分成几乎相等的两份，分别将两段中第一个最小的数拿出来放在一个临时数组中，直到全部取完。因为是递归的，所以每一段的数列都是排序好的。 1234567891011121314void merge_sort(ll *A,ll *B,int x,int y){ if(y-x<=1)return; int mid=x+(y-x)/2; int ...

点分治 点分治是一种树形分治的算法，它选择当前连通块一个重心，将树分成多个连通块进行处理，然后对每个连通块进行分治递归。 树的重心 树上的一个点，满足它的儿子的 \(size\) 的最大值最小。 可以证明，一个树有一个或者两个重心。若有两个重心，它俩一定是直接相连的。 处理问题 求树上给定路径联通的点的对数。我们发现将树分治后，形成了若干个连通块，而且这些连通块必定经过重心。...