单调栈的本质与应用
- 2022 年 9 月 28 日
- 笔记
单调栈的定义与证明 前言 最近领悟到了单调栈的本质，特此来记录一下我的理解。 单调栈主要用来解决这样一类问题，当 …
Continue Reading线段树学习笔记（基础&进阶）（一） | P3372 【模板】线段树 1 题解
- 2022 年 9 月 26 日
- 笔记
什么是线段树 线段树是一棵二叉树，每个结点存储需维护的信息，一般用于处理区间最值、区间和等问题。 线段树的用处 对编号连 …
Continue ReadingP4315 月下“毛景树”(树链剖分)
- 2022 年 8 月 6 日
- 笔记
P4315 月下“毛景树”(树链剖分) 题面 简述: 边权转点权(在dfs1处转换) 把一条边权赋值在深度更深的上 需要 …
Continue Reading线段树杂谈
- 2022 年 7 月 24 日
- 笔记
概念： 线段树（Segment Tree）是一个基于分治的数据结构。 通常处理区间，序列中的查询，更改问题。大体上有单修 …
Continue Reading“ 学习笔记 ”线段树合并
- 2022 年 3 月 10 日
- 笔记
线段树合并 普通线段树 \((\) 无懒惰标记 \()\) 时间复杂度 & 空间复杂度 假设有 \(2\) 棵线 …
Continue Reading“ 题解 ”P2487 [SDOI2011]拦截导弹
- 2022 年 2 月 12 日
- 笔记
简单题意 给定 \(n\) 个数对 \((h_i, v_i)\)。 求： 最长不上升子序列的长度。 对于每个 \(i\) …
Continue Reading线段树
- 2021 年 9 月 24 日
- 笔记
要解决的问题 数组任意区间内的元素修改，增加，求和，时间复杂度都要达到O(logN)水平, 方法说明如下 L…R上都 …
Continue Reading[题解] CF786B Legacy
- 2021 年 5 月 15 日
- 笔记
前言 题目链接 题意 有 \(n\) 个点，\(q\) 次连边，以及起点 \(s\) 。连边具体分三种： \(1\) \ …
Continue Reading
[题解] T’ill It’s Over
- 2021 年 4 月 2 日
- 笔记
前言 线段树+网络最大流的建模题。 题目链接 题目大意 最初时有 \(n\) 个 \(1\) 。给定 \(op\) 、 …
Continue Reading
树链剖分解析
- 2021 年 3 月 6 日
- 笔记
前置知识 线段树 \(and\) 树上基本操作 定义 几个在树链剖分很重要的概念。 重儿子 对于一个父节点，含有节点数最 …
Continue Reading