TH911 Blog

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

题解：[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...

Posted by TH911 on August 18, 2025

题解：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...

Posted by TH911 on August 16, 2025

题解：序列

洛谷P5350

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

Posted by TH911 on August 16, 2025

ODT 珂朵莉树详解

例题：CF896C

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

Posted by TH911 on August 16, 2025

题解：[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...

Posted by TH911 on August 16, 2025

题解：[春季测试 2023] 圣诞树

洛谷P9119

题目传送门 题意分析 首先确定起点 $k$ 是简单的。记 $a_1,a_2,\cdots,a_n$ 为原来的 $n$ 个点。 可以统一将 $a_1,a_2,\cdots,a_k$ 与 $a_{k+1},a_{k+2},\cdots,a_n$ 交换在序列中的位置，这样便于处理。交换后仍然为凸多边形。 考虑原问题等价于对新的 $a_1,a_2,\cdots,a_{n-1}$ 进行...

Posted by TH911 on August 16, 2025

各类模板

矩阵乘法 Barrett 约减

矩阵乘法 Matrix，支持二维 initializer_list 初始化。支持矩阵加法、矩阵乘法。重载 +、+=、*、*=。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47...

Posted by TH911 on August 15, 2025

Barrett 约减

优化整数除法/取模

推荐一篇文章。 Barrett 约减优化整数除法/取模 取变量的模其实是非常慢的，而 Barrett 可以在一定情况下将取模化为两次乘法、一次右移以及至多两次减法。 令模数为 $p$。 容易发现： \[x\bmod p=x-p\left\lfloor\dfrac xp\right\rfloor\] 考虑快速求出 $\left\lfloor\dfrac xp\right\r...

Posted by TH911 on August 15, 2025

线段树历史操作

历史和线段树

历史和线段树 例题：Loj P193 线段树历史和 您需要写一种数据结构，来维护一个有序数列，其中需要提供以下操作： 区间加一个数。 查询区间的历史和。 历史和定义为数列 $h_i$ 的区间和：初始 $h_i=a_i$，在每次操作（修改或查询）完成后，对所有 $h_i \leftarrow h_i+a_i$。 考虑使用线段树维护区间信息。...

Posted by TH911 on August 15, 2025

题解：Koishi Loves Number Theory

洛谷P3598

题目传送门 数学推导 首先不难得到： \[\begin{aligned} f(n)&=\sum_{i=0}^nx^i\\ &=\dfrac{x^{n+1}-1}{x-1} \end{aligned}\] 因为 $\operatorname{lcm}\left(\dfrac ac,\dfrac bc\right)=\dfrac{\operatorname{lcm...

Posted by TH911 on August 14, 2025

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS