12k 字 17 分钟

# Day 0 上午自然是摸了在家里收拾东西，收着收着就装了两个箱子，不知道哪里来的这么多东西…… 下午 2:30 的飞机，想来也是好久没去重庆了，虽然老家在重庆，但是上一次去大概是好几年前了。 印象深刻的是有一次从重庆江北机场坐回石家庄的飞机，晚点了，用候机厅的电脑打了 3h 游戏…… 最后飞机实在飞不了，还在附近酒店住了一晚上第二天才起飞。 ShuKuang\text{\color{black}S\color{Red}{huKuang}}ShuKuang 没做过飞机，非常害怕，在网上搜索了一下历史上波音-738\text{-738}-738 的事故，发现全是...
16k 字 21 分钟

# 前置芝士 重链剖分（最好是熟练掌握） 莫队（大概了解即可，有一点相似的思想） dfs 序（可有可无，主要是为了加速，其实我就没写过 QwQQwQQwQ） # 主要思想 dsu on treedsu\ on\ treedsu on tree 又名树上启发式合并 （其实是非常暴力的一个东西。） # 用途 可处理树上的一些统计类型的问题。 如： 求子树中颜色最多的颜色编号之和，相同数量都要加上 CF600E Lomsat gelral 给一棵树，树上每个节点都有一个颜色，求已点 uuu 为根的子树中，出现次数 >=k>= k>=k...
3.4k 字 5 分钟

# Description Luogu 传送门 # Solution 挺板子的平衡树。 题目要求我们支持三个操作： 插入 / 更新 一个点的值。 查询一个点的排名。 查询从第 xxx 名开始后面最多 10 名玩家的名字。 这些操作看着就很板子。。 唯一比较恶心的是要 hash\text{hash}hash 一下，所以开个 map\text{map}map 存一下编号。 小技巧，存每个人的得分时存负数，这样 split\text{split}split 时的边界要稍微好调一点。 传参数一定要写对啊，千万不要像我一样打错了调半天 QwQ #include...
2.6k 字 3 分钟

# Description Luogu 传送门 # Solution 区间 dp # 状态定义 根据套路，我们定义 dp[i][j]dp[i][j]dp[i][j] 表示取走区间 [i,j][i, j][i,j] 的最小花费。 但是只有区间范围似乎并不好转移，因为我们也不知道区间最大值以及最小值是多少。 所以我们再定义一个 f[i][j][x][y]f[i][j][x][y]f[i][j][x][y] 数组，表示区间 [i,j][i, j][i,j] 中所有数在区间 [x,y][x, y][x,y] 时，需要的最小花费。 注意：这里...
6.3k 字 9 分钟

# 浅谈 fhq-treap（无旋 treap） 模板题：洛谷 P6136 【模板】普通平衡树（数据加强版） （emm 刚写了这个，就放这个吧） fhq−treapfhq-treapfhq−treap 也叫做 无旋 treap，由范浩强大佬发明。 个人认为是平衡树中码量最少，也最容易理解的一种写法。 # 主要思想 顾名思义，无旋意味着它没有旋转操作（终于没有恶心人的旋转了）。 事实上，无旋 treap 只有两种操作。 一种是 splitsplitsplit（分裂），另一种是 mergemergemerge（合并）。 平衡树中的各种操作都可以用这两个函数来搞定。下面我们来一一分析。 #...
8.5k 字 12 分钟

# 树链剖分（重链剖分） 模板：洛谷 P3384 【模板】轻重链剖分 / 树链剖分 写在前面：强烈建议初学的同学如果不理解的话先手写一遍（像我一样），非常有助于理解 # 概念： 重儿子： 一个节点所有儿子中最大的儿子 轻儿子： 一个节点除重儿子之外的其他儿子 特别地，叶子节点既没有重儿子也没有轻儿子 重链： 重儿子连接形成的链叫重链 # 主要思想： 把一颗树拆成许多条链，把树上操作改为链上操作（区间操作），并利用线段树或树状数组等数据结构维护，以降低时间复杂度 每次进行操作时，先修改重链，再修改轻链 # 常见操作： 将树从 xxx 到 yyy 结点最短路径上所有节点的值都加上...
8.4k 字 11 分钟

# 前言 模拟赛上考了一道反悔贪心，然而根本不会，于是蒟蒻就学习了一下。 # 概念 顾名思义，反悔贪心是反悔 + 贪心。 贪心一般来讲是没有撤销操作的，因为你贪心就是要贪最优解，哪里来的撤销呢？ 但是有的时候你贪心出来的 “最优解”...
4.2k 字 6 分钟

洛谷 P4556 [Vani 有约会] 雨天的尾巴 /【模板】线段树合并 # 主要思想： 顾名思义，线段是合并就是将多棵线段树合并到一起，要求线段树维护的数据可以支持合并，例如最大值，区间和等。 我们在进行合并时要把两棵线段树上相同的结构点合并到一起，换句话说，就是两棵线段树当前要合并的点所表示的区间是一样的。 例如，区间长度是 888，那么我们合并时要把 [1,8][1,8][1,8] 和 [1,8][1,8][1,8] 合并到一起 [5,8][5,8][5,8] 和 [5,8][5,8][5,8] 合并到一起。 好了，我们知道了主要思想后下面来看如何实现。 # 题解： 对于洛谷...
5.7k 字 8 分钟

# Day -1 今天有 tbl 学长的课，害怕.jpg 上午不出意外的被 D 了 QwQ 可能是因为在二南的时候听过了一次 tbl 学长的课，所以这次听的时候有了点心理准备，受到的折磨没有想象中的那么大。 晚上大家一起在机房打了一场 ABC，结果集体降智，一个小时硬是没切掉 F，自闭了。 好不容易挺过了今天，晚上回家调了调网络流洗了个澡就睡了。 # Day 0 上午简单收了收东西，由于不用带被子被褥什么的，所以也没有什么需要带的。 吃午饭的时候看了男子冰球决赛，俄罗斯奥委会对战芬兰，看的时候已经 1​ : 1​ 了，本来还等着看无限加时赛呢，结果芬兰第三节不到 1...