TH911 Blog

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

树状数组详解

例题：树状数组 1（P3374）、树状数组 2（P3368）、守墓人（P2357）

题目传送门：树状数组 1、树状数组 2 、守墓人 防止日后忘记。 引入 例题 $1$： 已知一个数列，你需要进行下面两种操作： 将某一个数加上 $x$。 求出某区间每一个数的和。 对于操作 $1$，我们可以直接通过普通数组 $\mathcal O(1)$ 实现修改。 对于操作 $2$，我们可以通过前缀和 $\mathcal O...

Posted by TH911 on December 14, 2024

《三体》电子书

三体I：地球往事 三体II：黑暗森林 三体III：死神永生

Posted by TH911 on December 14, 2024

题解：贪婪大陆

洛谷P2184

题目传送门 树状数组 我们开两个权值树状数组 $tl,tr$，分别存储布雷的左、右边界。 那么对于给定区间 $[l,r]$，答案即 $tl.query(r)-tr.query(l-1)$。 如图： 蓝色即布雷区间，黑色即查询区间。 $\color{black}\colorbox{black}{1}$ 黑色右区间之前的 $\color{skyblue}\colorbox...

Posted by TH911 on December 14, 2024

题解：色板游戏

洛谷P1558

题目传送门 $30$ 棵线段树 我们对于每一种颜色 $i$ 都开一棵线段树 $t[i]$ 维护区间是否染上了该颜色。 判断是否染上了该颜色只需要判断该区间内是否有 $1$。 维护区间最大值或者 bool || 运算即可。 代码： 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...

Posted by TH911 on December 14, 2024

题解：黑匣子

洛谷P1801

题目传送门 题意分析 与中位数类似，不过这里是给定 $i$，求第 $i$ 大。 本文给出对顶堆做法，其余做法请参考中位数。 还是这张图。 维护一个大根堆 $x$ 和一个小根堆 $y$，让 $x$ 中的元素小于 $y$ 中的元素，即 $x.top()<y.top()$。 在我们加入元素 $p$ 时，先将 $p$ 加入 $x$，同时保持 $x.size()<i...

Posted by TH911 on December 14, 2024

题解：无聊的数列

洛谷P1438

题目传送门 和守墓人类似，可以使用“二阶差分+树状数组”解决。 本文提供一种“一阶差分+线段树”的做法。 题意分析 将原数组差分后，操作 $1$ 即： \[a_l\leftarrow a_l+k\\ a_{l+1}\leftarrow a_{l+1}+d\\ a_{l+1}\leftarrow a_{l+1}+d\\ a_{l+1}\leftarrow a_{l+1}+...

Posted by TH911 on December 14, 2024

题解：中位数

洛谷P1168

题目传送门 权值树状数组 很好理解，$i$ 枚举 $1\sim n$，每次往权值状数组中加入 $a_i$，这样我们就能知道对于一个数 $x$，$a[1…i]$ 中小于等于 $x$ 的数的个数。 二分答案，在值域上二分第 $k$ 大的数，时间复杂度，$\mathcal O(n\log^2 n)$。 倍增查询最大的 $pl$ 使得 $a[1…i]...

Posted by TH911 on December 14, 2024

题解：[AHOI2009] 维护序列

洛谷P2023

题目传送门 与 线段树 2 几乎一模一样，直接放出代码。 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 48 49 50 51 52 53 54 55 56 57 ...

Posted by TH911 on December 14, 2024

线段树详解

例题：线段树1（P3372）、线段树2（P3373）、[AHOI2009] 维护序列

之后很长一段时间都不会怎么深度碰 OI 了，防止哪天自己忘掉。 线段树 1 传送门 线段树 2 传送门 [AHOI2009] 维护序列 作用 线段树是算法竞赛中常用的用来维护区间信息的数据结构。 线段树可以在 $\mathcal O\left(\log n\right)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操...

Posted by TH911 on December 13, 2024

题解：[ARC173D] Bracket Walk

AtCoder ARC173D

题目传送门 题意分析 给定一张图，每一条边都对应着一个 ( 或 )，构造一条路径使得最终形成的括号序列是合法的。 首先，这个序列想要合法，长度肯定得是偶数，且其中 (、) 的数量相等。 那么我们将序列分开来看，已经能够匹配上的 ( 和 ) 先不管，那么匹配不了的只能形如 )...(。（否则就匹配上了） 考虑到合法路径一定是个环（起点、终点相同），因此我们可以通过更换起点的方...

Posted by TH911 on November 28, 2024

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

要做一个优秀的 OIER

FRIENDS