RainAir
My OI Blog
RainAir

树链剖分
文章归档

DDP 学习笔记

DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡,现在回来学一学。 我们来找一…

   167   2019-07-11 去围观

「CF487E」Tourists

题目链接 题目描述 给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作,要么修改一个点的点权,要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径,路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $. 题解 问的是所有可能路径上的最小点权的最小值,那我们…

   356   2019-01-23 去围观

月下毛景树

题目链接 题目描述 给定一棵 $ N $ 个节点的树,需要维持以下个操作: 改变第 $ k $ 条边的边权; 改变点 $ u $ 到点 $ v $ 的边权为 $ w $; 将点 $ u $ 和点 $ v $ 路径上的边的边权都增加 $ w $; 询问点 $ u $ 和点 $ v $ 路径上的边权最大值。 其中 $ 1 \l…

   276   2018-08-22 去围观

「HAOI2015」树上操作

题目链接 这一道题的题解在luogu上的链接 解题报告 这一题是树链剖分的板子题。 什么?你不会树链剖分?点这里学习 对于操作1:直接在点的dfn在线段树的位置修改即可。 对于操作2:我们考虑在记录每个以该点为根的子树大小时,由于dfn的顺序一定是子树的dfn小…

   344   2018-07-12 去围观

树链剖分学习笔记

树链剖分是一种树路径信息维护算法。 把整棵树划分成许多条链,使每个节点都在唯一的链上,对每一条链维护一棵线段树,把在树上的操作转移到线段树上。 ž将一棵树划分成若干条链,用数据结构去维护每条链,保证每个点在且仅在一条链上,通过数据结构维护这些链的信息…

   437   2018-06-18 去围观
标签
近期评论