多重背包 01 背包中每个物品只有一个，而多重背包中每个物品有 $s_i$ 个。 多重背包二进制优化 对于第 $i$ 个物品，如果它有 $s_i$ 个，就将其用二进制拆分，然后转成 01

友情出场本次HDU新生赛，题目质量一如既往的优秀。写一下解题报告吧。 题目 & 题解 题目PDF 题解PDF Q1 选课 题意 有一些学生档案，每个档案上记录了

介绍 树上差分就是将数组上的差分思想，转化到树上。 树上差分是一种思想，很多时候树链剖分可以代替树上差分，如果询问不复杂的时候，就可以用树上差分

介绍 主席树全名叫做 可持久化权值线段树，一般用于一个数组上，有以下的功能： 对于每一个区间 都能 开一个权值线段树。 能够维护数组的 历史版本。（仅用于

介绍 权值线段树 权值线段树用于维护一定值域内，各个元素出现的次数，结合动态开点可以 避免离散化的处理。 举个例子，我们现在有一个长度为 $10$ 的数组 $[1,5,2,3,4,1,3,4,4,4]$ $1$

题目链接 题意 给定正整数 $c,d,x$，求正整数pair $(a,b)$ 的数量使得 $$c \times lcm(a,b) - d \times gcd(a,b) = x$$ 其中，共 $T \leq 10^4$ 个testcase，$1 \leq c,d,x \leq 10^7$ • $(a,b)$ 和 $(b,a)$ 不

介绍 数位DP是指这样一类题型： 给定一些限定条件，求 $[L,R]$ 内满足这些条件的数字数量，一般 $L,R$ 可能非常大（例如$10^{18}, 10^{1000}$）

主要记录一些遇到的线段树/分块例题。 例1 CF438D 题意 给定 $N$ 个正整数和 $M$ 个询问，询问有 3 种： $1 ~ l ~ r$：输出 $\sum\limits_{i=l}^r a_i$ $2 ~ l ~ r ~ x$：将 $a_l$ 到 $a_r$ 的所有数

介绍 树上启发式合并 一般用于 满足以下条件的问题： 所有询问离线，无修改，仅询问子树的信息（不能用于链的询问） $ans[u]$ 可以转化为 $\sum\limits_{v}ans[v]$ 的形式（其中，$v$ 是

题目链接 https://atcoder.jp/contests/abc131/tasks/abc131_f 题意 给定 $N$ 个二维平面中的点 $(x_i,y_i)$，我们可以一直重复以下操作： 选择 4 个整数 $a,b,c,d$，保证 $(a,b),(a,d),(c,b),(c,d)$ 中 有且仅有 3 个点