搜索结果
查询Tags标签： 剖分，共有 18条记录-
编程兔暑假3.5阶段集训Day3——线段树后半部分、可持久化线段树、树状数组、倍增求LCA、树上差分、三种剖分以及搜索
我们接着昨天的讲。懒标记是线段树中一个十分重要的知识点，在线段树中进行区间修改时，暴力的做法是递归到叶子结点修改信息，复杂度达到了O(n) ，不过我们可以将这些修改操作攒起来，到了合适的时候一起修改，这就是懒标记。对于线段树上的每一个结点，引入一个标记，记…
2022/7/28 1:52:55 人评论 次浏览 -
洛谷 P3384 【模板】轻重链剖分/树链剖分
【模板】轻重链剖分/树链剖分 题目描述 如题，已知一棵包含 \(N\) 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上…
2022/7/23 6:25:22 人评论 次浏览 -
HYSBZ1036 [ZJOI2008]树的统计（树链剖分）
将树通过树链剖分转化成线性序列，用线段树维护最值，和值即可。1 #include<iostream>2 #include<cstdio>3 #include<cstring>4 #include<algorithm>5 using namespace std;6 const int maxn=30005;7 int n,m;8 int head[maxn],to[maxn<<1]…
2022/7/1 23:23:44 人评论 次浏览 -
树链剖分学习笔记
树链剖(pōu)分定义 树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。 树链剖分有多种形式，如重链剖分、长链剖分等，通常说的树链剖分指重链剖分。 重链剖分 首先给出一些定义：重子节点：所有子节点中子树大小最大的子节点轻子节点：除重子节点的其它子节…
2022/4/28 23:12:39 人评论 次浏览 -
2022.4.10#树链剖分=链式前向星+dfs序+lca思想+线段树
2022-04-10 树链剖分，理解完只有惊叹。 前置知识： 链式前向星： 需要的变量： cnt 记录边数 edges{ to,w,next}的数组，存储边 head[maxn]存储每个节点的最新的那条边1 //链式前向星，储存图的方式，思想是前向2 //相当于一个邻接表的每一行的链表，向最前端插入3 4 #in…
2022/4/10 23:44:39 人评论 次浏览 -
【模拟赛】乌拉~~（重链剖分）
背景大家好，我是一名勇敢的俄罗斯士兵，我昨天正在打 CodeForces\tt CodeForcesCodeForces 呢，突然被拉去打仗了。我们已经突入基辅，但因为推进过于迅速，后勤补给未能补上，我们现在急需 143 元来购买一些吃的 一个能替代通信员的老兄来解密一下临时截获的乌克兰电报，…
2022/2/25 23:52:11 人评论 次浏览 -
「USACO11DEC」Grass Planting G 题解 (树链剖分)
题目简介 给出一棵 \(N\) 个节点的树，有 \(M\) 个操作，操作为将一条路径上的边权加一或询问某条边的权值。 分析 点差分与边差分的区别是：点差分计入 \(lca\) ，边差分不计 \(lca\)。 模板树链剖分是对点统计，类似点差分。 本题是对边统计，只需要去掉 \(lca\) 的计算…
2022/2/17 23:14:58 人评论 次浏览 -
PCL贪婪的三角剖分算法gp3
介绍：点云贪心三角化 输入pcd文件，输出vtk文件。 主要就是一下两个参数： 设置用于确定用于三角测量的最近邻的球面半径 gpt.setSearchRadius (radius); 设置最近邻距离的乘法器，得到每个点的最终搜索半径(这将使算法适应云中不同的点密度)。 gpt.setMu (mu); 代码如下…
2021/11/25 9:10:53 人评论 次浏览 -
PCL贪婪的三角剖分算法gp3
介绍：点云贪心三角化 输入pcd文件，输出vtk文件。 主要就是一下两个参数： 设置用于确定用于三角测量的最近邻的球面半径 gpt.setSearchRadius (radius); 设置最近邻距离的乘法器，得到每个点的最终搜索半径(这将使算法适应云中不同的点密度)。 gpt.setMu (mu); 代码如下…
2021/11/25 9:10:53 人评论 次浏览 -
树链剖分学习笔记（二）
上一篇：树链剖分学习笔记（一） 这篇是长链剖分 并没有仔细研究过这方面的内容，所以就随便写点简单的东西了 1. 概念 长链剖分也是一种树链剖分，所以和轻重链剖分很相似 区别是长链剖分选择子树深度最大的儿子作为重儿子，而不是子树大小最大的 它也具有一些性质：链长…
2021/11/18 6:11:48 人评论 次浏览 -
树链剖分学习笔记（二）
上一篇：树链剖分学习笔记（一） 这篇是长链剖分 并没有仔细研究过这方面的内容，所以就随便写点简单的东西了 1. 概念 长链剖分也是一种树链剖分，所以和轻重链剖分很相似 区别是长链剖分选择子树深度最大的儿子作为重儿子，而不是子树大小最大的 它也具有一些性质：链长…
2021/11/18 6:11:48 人评论 次浏览 -
P2146 [NOI2015] 软件包管理器(树链剖分)
题目背景Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/U…
2021/10/28 6:11:25 人评论 次浏览 -
P2146 [NOI2015] 软件包管理器(树链剖分)
题目背景Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/U…
2021/10/28 6:11:25 人评论 次浏览 -
dfs序与树链剖分
dfs序与树链剖分本文根据以下视频整理 链接 引子 先看一个题: 已知一棵树，每个节点包含一个权值，你需要设法实现以下操作操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有结点的值加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有结点的值之和 操作3:…
2021/8/18 6:07:53 人评论 次浏览 -
dfs序与树链剖分
dfs序与树链剖分本文根据以下视频整理 链接 引子 先看一个题: 已知一棵树，每个节点包含一个权值，你需要设法实现以下操作操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有结点的值加上z 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有结点的值之和 操作3:…
2021/8/18 6:07:53 人评论 次浏览
