Home
SSC Studio
Cancel

LCA

GCD及其证明

「欧几里得算法」应该是刚入门算法就要学会的·了·吧… 奈何我一直拖到现在还没有为它写过一篇博客. 今天顺手将它补上. 最大公约数即为 Greatest Common Divisor, 常缩写为 gcd. $\pm 1$ 是任意一组整数的公约数. 代码模板 int gcd(int a, int b) { if (b == 0) return a; return gcd(...

Some Tricks

快读函数 写一个「快速读入」函数: inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } whil...

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)$. 归并...