2025 Summer Day1

2025 Summer Day1 Content：Data Structs Date：2025.7.17 内容 并查集 ST表 线段树 关于树状数组 一维树状数组 单点修改，区间查询 对于这一类最普通的树状数组，没有什么好说的，直接维护前缀和即可。 struct BIT { long long

2025 Summer Day2

2025 Summer Day2 Content：Segment Tree Date：2025.7.18 主题 线段树进阶 关于线段树 区间操作 对于区间开根号我们可以记录最大值和最小值，然后维护极差，由此将区间开根号转化为区间加和区间覆盖问题，减小修改操作的复杂(度，均摊后复杂度为 \Theta(

2025 Summer Day3

2025 Summer Day3 Content： Data structs Date：2025.7.19 内容 三维偏序问题 CDQ分治 整体二分 分块 莫队算法 具体内容 三维偏序问题 问题描述 给定一些三元组 (a_i, b_i, c_i)，询问对于三元组 (a_j, b_j, c_j)，有多

2025 Summer Day4

2025 Summer Day4 Content：Math Date：2025.7.20 内容 矩阵 线性方程组 行列式 矩阵树定理 线性基 具体内容 矩阵 矩阵定义 定义 将一些元素排列成若干行，每行放上相同数量的元素，就是一个矩阵 (Matrix)。 对于矩阵 A 的第 i 行，第 j 列，我们

2025 Summer Day5

2025 Summer Day5 Content: Problem on Tree Date：2025.7.21 概览 树的重心 树上启发式合并 树链剖分 左偏树 点分治 具体内容 树的重心 定义 树的重心是满足如下条件的点 u: 树上不存在其他节点 v，使得 \max\{\operatorname

2025 Summer Day6

2025 Summer Day6 Content：Data Structures; Date：2025.7.22 概览 可持久化线段树 虚树 具体内容 可持久化线段树 可持久化线段树实现可持久化数组 我们对每一个版本维护一颗线段树，这样显然空间复杂度是 \Theta(nm) 的，肯定不对。 接下来我

2025 Summer Day7

2025 Summer Day7 Content：Competition Date：2025.7.23 T1：宝宝巴士之小猫数数 赛时思路 开始题意理解错了，以为是倒数第二位开始的连续的 0，后面也没有什么新的思路，就用 python 打了个 n \le 5000 的表，拿了 50 分的部分分。 正

2025 Summer Day9

2025 Summer Day9 Content：DP (state, num) Date：2025.7.25 概览 数位 DP 状压 DP 内容 状压 DP 状压 DP，即状态压缩 DP，通常情况下和子集问题挂钩，以二进制的第 i 位表示集合中的每个子集选还是不选。 有一种 O(3^n) 的子集枚

2025 Summer Day10

2025 Summer Day10 Content：dp优化 Date：2025.7.26 例题 洛谷-P1886 滑动窗口 思路 直接单调队列维护即可，具体操作如下： 每次查看队尾的元素，维护单调性。 对于队头不在当前滑动窗口的元素，弹出。 提交记录：link 洛谷-P2365 任务安排<

2025 Summer Day8

2025 Summer Day8 Content：DP (Interval, Tree) Date：2025.7.24 概览 区间 DP 树形 DP 例题 洛谷-P4516 潜入行动 题目大意 题目大意 给定一颗树，要求在树上选取恰好 \large k 个节点 (不得重复)，每个选取的节点可以覆盖它