TH911 Blog

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

树状数组详解

例题:树状数组 1(P3374)、树状数组 2(P3368)、守墓人(P2357)

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

《三体》电子书

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

题解:贪婪大陆

洛谷P2184

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

题解:色板游戏

洛谷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...

题解:黑匣子

洛谷P1801

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

题解:无聊的数列

洛谷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}+...

题解:中位数

洛谷P1168

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

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

线段树详解

例题:线段树1(P3372)、线段树2(P3373)、[AHOI2009] 维护序列

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

题解:[ARC173D] Bracket Walk

AtCoder ARC173D

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