TH911 Blog

「光阴不可测,岁月亦无歌。」

李超线段树

例题:洛谷P4097

例题链接 要求在平面直角坐标系下维护两个操作: 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。 给定一个数 $k$,询问与直线 $x = k$ 相交的线段中,交点纵坐标最大的线段的编号。 特别地,如果线段是竖直的,则取最上面的点。线段若不存在,则输出 $0$。 ...

题解:[ZJOI2007] 仓库建设

洛谷P2120

题目传送门 朴素 DP 记 $\textit{dp}_i$ 表示第 $i$ 个工厂必须建仓库,第 $1\sim i$ 个工厂的总花费。 则有: \[\begin{aligned} \textit{dp}_i&=c_i+\min_{j=0}^{i-1}\left(\textit{dp}_j+\sum_{k=j+1}^i(x_i-x_k)p_k\right)\\ &...

斜率优化 DP 详解

例题:洛谷P3195

传统斜率优化 DP 例题:洛谷 P3195 [HNOI2008] 玩具装箱。 给定正整数 $n,L$ 和数列 $a_1,a_2,a_3,\cdots,a_n$。$1\leq n\leq5\times10^4$。 将 $a$ 划分为 $k$ 段,设第 $i$ 段为 $a_{l_i},a_{l_i+1},\cdots,a_{r_i}$,则记 $\displaystyle x_...

题解:[HNOI2004] 敲砖块

洛谷P1437

题目传送门 题意分析 发现一块砖 $(i,j)$ 被打掉之后,第 $j$ 列在 $i$ 上面的砖都会被打掉。 设 $\textit{dp}_{i,j,k}$ 表示第 $i$ 列中,打掉的最下面的砖为 $(j,i)$,一共打掉了 $k$ 块砖的答案。 则有: \[\textit{dp}_{i,j,k}=\max_{l=0}^{j+1}\textit{dp}_{i-1,l,k-...

题解:[SDOI2015] 约数个数和

洛谷P3327

题目传送门 题意分析 不妨令 $n\leq m$。 首先,答案为: \[\sum_{i=1}^n\sum_{j=1}^md(ij)\] 这个 $d(ij)$ 表示 $ij$ 的约数个数,很不好处理。 因此可以考虑 $d(ij)$ 能否化简,有: \[d(ij)=\sum_{x\mid i}\sum_{y\mid i}[x\perp y]\] 证明参见此处。 因此可以...

题解:[HEOI2016/TJOI2016] 排序

洛谷P2824 | ODT 维护。

题目传送门 问题转化 发现询问有且仅有一次,且仅询问一个位置。 因此无需得出整个序列,得出排序后的 $a_q$ 即可。区间排序实在不好做,因此考虑能否找到一种方式转化。 答案与 $a_q$ 正相关,其余其实并不重要。因此不妨有: \[a_i\leftarrow \begin{cases} 1&a_i\geq a_q\\ 0&a_i<a_q \end{c...

题解:Physical Education Lessons

CF915E

题目传送门 题意分析 操作即区间赋值为 $0$ 或 $1$,求 $1$ 的个数。 显然可以 ODT 维护。 注意不要滥用 perform 操作,而应当维护全局标记。 因为不存在 perform 操作,故有时间复杂度:$\mathcal O(q\log n)$。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2...

题解:序列

洛谷P5350

题目传送门 ODT 珂朵莉树 如果你不会,你可以看看:ODT 珂朵莉树。 数据随机,且有区间赋值,因此考虑 ODT。 操作 $1\sim3$ 是简单的,考虑操作 $4\sim6$。 操作 $4$:区间复制 区间不交,分别 split 操作后,暴力记录 $[l_1,r_1]$ 的信息,删除 $[l_2,r_2]$ 的信息再插入记录信息即可。 同时注意区间端点需要偏...

ODT 珂朵莉树详解

例题:CF896C

珂朵莉树(ODT)是一种在随机数据下复杂度优秀的维护存在区间赋值操作的数据结构。 在随机数据下,期望不同的值的个数并不多,因此可以合为一个节点处理,便得到了珂朵莉树。 ODT 珂朵莉树 例题:CF896C Willem, Chtholly and Seniorious 给定序列 $a_1,a_2,\cdots,a_n$。维护操作: 将 $a_l,...

题解:[CSP-S2019] Emiya 家今天的饭

洛谷P5664

题目传送门 题意分析 原来的 $a$ 可以视为一个矩阵。接下来的「行」「列」即矩阵意义下的行/列,「行」代表「烹饪方法」,「列」代表「主要食材」。 不考虑小于等于 \(\left\lfloor\dfrac k2\right\rfloor\) 的限制,不难发现,所有的方案数为: \(\prod_{i=1}^n\left(\sum_{j=1}^ma_{i,j}+1\right)-1...