TH911 Blog

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

题解：[SCOI2010] 序列操作

洛谷P2572

题目传送门 题意分析 我们需要维护一种数据结构来维护 $0,1$ 区间的信息，使其能够高效的获取区间内 $1$ 的数量和最多的连续的 $1$ 的数量，并能够高效的将指定区间赋为指定值和实现区间翻转（注意是值取反，而不是类似于字符串的翻转）。 维护区间信息 线段树节点维护信息 维护区间信息，自然而然地想到线段树。 那么需要维护哪些信息呢？ 一般地，区间边界 $l,r$。 ...

Posted by TH911 on December 21, 2024

题解：三元上升子序列

洛谷P1637

题目传送门 题意分析 通过树状数组可以在 $\mathcal O(n\log n)$ 的时间内求出所有 $i<j$ 且 $a_i<a_j$ 的 $(i,j)$ 的个数。 仅仅需要在从左向右遍历的过程中在权值树状数组中查询小于等于 $a_i-1$ 的个数并加入 $a_i$ 即可。 那么我们需要求出所有 $i<j<k$ 且 $a_i<a_j<a...

Posted by TH911 on December 21, 2024

树状数组详解

例题：树状数组 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

题解：[CSP-S 2022] 策略游戏

洛谷P8818

题目传送门 题意分析 AC 代码 1

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

FEATURED TAGS
普及+/提高 题解 提高+/省选− 线段树 数学 贪心 倍增算法 树状数组 LCA 前端 字符串 普及/提高− 未完 树链剖分 模拟 RMQ ST表 二分 前缀和 堆 字典树 对顶堆 差分 平衡树 搜索 省选/NOI− 队列 C++错误合集 FHQ Treap KMP Manacher
ABOUT ME

要做一个优秀的 OIER

FRIENDS