Home
SSC Studio
Cancel

ST表

ST(Sparse Table)表,中文名稀疏表,是一种数据结构。 ST表常用于解决可重复贡献问题. 不知道什么是「可重复贡献问题」? 一句话解释, 就是: 对于运算 op, 有 x op x = x. 想要详细了解可以去查一查. 常见的可重复贡献问题有: 区间最值、区间按位和、区间按位或、区间 GCD 等. 而像区间和这样的问题就不是可重复贡献问题. P3865 【模板】S...

单调栈

单调栈是满足单调性的栈结构, 即实时维护栈内部的元素满足某种单调性. 将一个元素插入单调栈时,为了维护栈的单调性,需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。 P5788 【模板】单调栈 例题 题意: 输入 n 个数, 找到每个数在它后面输入的数中第一个比它大的数的下标. 思路: 栈要么为空, 要么满足里面的数是单调不增的. 每输入一个数, 就和栈顶元素比...

RMQ问题

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。 问题的形式就是, 给定一个长度为 n 的数组, 每次查询一个区间, 要求返回这个区间内的最值. 具体有下面几种方法来解决 RMQ 问题. 单调栈 ST 表

线段树和树状数组

线段树 线段树是用来维护区间信息的数据结构. 线段树可以在 $O(\log{n})$ 的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。 线段树将每个长度不为 1 的区间划分成左右两个区间递归求解,把整个线段划分为一个树形结构,通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便地进行大部分的区间操作。 有个大小为 5 的数组 a...

求逆序对: AcWing 107 超快速排序

Link 仔细想想, 这道题就是求逆序对. 再就是注意结果要用 long long. 归并排序解法 #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <string> #include <strin...

对顶堆的应用: AcWing 106 动态中位数

Link 每当数据集中有奇数个数据时, 就查询一次中位数. 可以想到用堆排序 (也即, 优先队列) 来做. 如果查询次数不是这么多的话, 其实还可以用树状数组. 我们都知道用优先队列可以“实时排序”, 但是优先队列是不能像数组那样「随机访问」的, 因此想要随时取出中位数就很麻烦, 需要 pop 出一半的数, 查完了还要 push 回去. 如果使用对顶堆, 事情就变简单了许多. 对于一个...

排序算法

Double Bubbles 还记得什么是稳定排序吗, C++ 里的稳定排序是 stable_sort, 原理是归并排序; 而 sort 是不稳定的, 原理是快速排序. 归并排序 归并排序 (merge sort) 是稳定排序算法. 归并排序基于分治思想将数组分段排序后合并, 时间复杂度在最优、最坏与平均情况下均为 $O(n\log{n})$, 空间复杂度为 $O(n)$. 归并...

二分

带领只会基础二分的「真正的蒟蒻」 (例如, 我) 进入一个二分新境界 AcWing 102 最佳牛围栏 Link 这道题的二分用在了找平均值上. 首先这个平均值并不是题目数据给出来的, 因此不能像别的二分题那样对数组索引进行二分; 况且, 这道题根本不用也不能对数组进行从大到小排序. 这道题的二分是在 n 块地中牛的数量上进行二分, 并且是用浮点数进行计算, 注意自定义精度判断...

快速幂

AcWing 90 64位整数乘法 Link 如果直接计算 a 乘 b 就会超过 long long 的最大范围, 所以采用快速幂的思想把 b 写成二进制形式, 如果第 i 位上为 1 就在结果上加 a*(1<<i), 并且每次加上之后取模就可以了. #include <iostream> #include <cstdio> #include &lt...

AcWing 1100 抓住那头牛

Link BFS 解法需要想清楚几种不可能发生的情况进行剪枝, 否则必定 TLE. 首先, 农夫不可能跳到负数坐标点, 不然只能通过向右跳一步回到 0, 既然这样当初就不该作出这个选择, 反而还多了一步. 因此这种情况必须排除. 而这种情况只可能发生在 cur-1 的时候, 因此在 cur-1 的时候判断. 而每个 cur 我们都是严格保持在 [0,N-1] 内的, 因此 cur-1 只...