xixike

二分答案，整除分块，dp + 推结论，曼哈顿转切比雪夫 + 4维区间dp

# 二项式反演 # 公式 fn=∑i=0n(ni)gi⇔gn=∑i=0n(−1)n−i(ni)fif_n = \sum_{i = 0}^n \dbinom {n}{i}g_i \Leftrightarrow g_n = \sum_{i = 0}^n (-1)^{n - i} \dbinom ni f_i fn​=i=0∑n​(in​)gi​⇔gn​=i=0∑n​(−1)n−i(in​)fi​ 证明就不细说了。那么二项式反演的式子有什么用呢？ 恰好和至多的转换： 设 fkf_kfk​ 为恰好 kkk 个的方案数，gkg_kgk​ 为至多 kkk 个的方案数（恰好 kkk 个和至多 kkk...

贪心 + 枚举，枚举 + 按位考虑，期望dp + 树形dp + 换根，线段树

set（并查集 + 时光倒流），树形dp + 数据分治，dp

斜率优化dp，莫队 + 线段树，权值线段树 + 线段树合并，数位dp

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

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

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

# 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]时，需要的最小花费。 注意：这里...

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