泪痕 @ 铁憨憨
辗转当作浮生妖,流离惊似尘世鬼
[ZJOI2006] 书架 [ZJOI2006] 书架
题意要求对一个元素互不相同的整数序列维护以下操作: 把某个数放到序列开头(左端) 把某个数放到序列结尾 把某个数和它左边的数交换 把某个数和它右边的数交换 询问某一个数字在序列的位置 询问在序列上某一位置的数是多少 $n,m\leq 8
2019.01.18
[HAOI2012] 高速公路 [HAOI2012] 高速公路
题意Y901 高速公路是一条由 段路以及 个收费站组成的东西向的链,收费站依次编号为 ,从收费站 行驶到 (或从 行驶到 ) 需要收取一定的费用,高速路刚建成时所有的
2019.01.17
并查集 ·Disjoint 并查集 ·Disjoint
摘要 并查集(Union-Find Set)用于处理元素间可传递的关系,通常以集合的方式呈现。 并查集本身又是一种树结构(由若干棵树组成的不相交森林),用树的根结点(代表元)来区分不同的集合。 并查集并查集支持以下基本操作: Get(
2018.12.19
Splay 初步 Splay 初步
2019.6.19 编入精选文章。 前言 平衡树是计算机科学中的一类改进的二叉查找树。一般的二叉查找树的查询复杂度是跟目标结点到树根的距离(即深度)有关,因此当结点的深度普遍较大时,查询的均摊复杂度会上升,为了更高效的查询,平衡树应运而生了
2018.12.19
线段树初步 线段树初步
线段树基础线段树,是利用一个区间建立一个完全二叉树,来快速实现区间修改、查询操作。 例如,要求对序列 A{1,3,4,2,5,3,7,8} 进行如下两种操作: add(l,r,v): 把 [l,r] 的元素都增加 v sum(l,r):
2018.12.19
树链剖分 ·Decomposition 树链剖分 ·Decomposition
摘要 树链剖分用于将树分割成若干条链的形式,以维护树上路径的信息。 具体来说,将整棵树剖分为若干条链,使它组合成线性结构,然后用其他的数据结构维护信息。 不同的剖分方案会导致不同的时间复杂度。在这其中极常见的是轻重链剖分(Heavy-Lig
2018.12.07
优先队列 | 二插堆 优先队列 | 二插堆
简介二叉堆的逻辑结构是一颗完全二叉树,然而它的实现却是用一维数组实现的。二叉堆分小根堆和大根堆。对于小根堆中的结点 x,其子树的所有结点键值均大于 x,即值越小的越靠近根结点,根结点的优先级最高。(大根堆同理)二叉堆常用于解决一些队列模拟问
2018.11.29
[SDOI2009]HH 的项链 [SDOI2009]HH 的项链
题意静态查询区间不同的数的个数 分析对询问按右端点排序 对于每个元素,更新它最后出现的位置,然后区间求个数 树状数组维护即可 复杂度 . 代码#include<cstdio> #include<al
2018.11.29
[LuoguP1637] 三元上升子序列 [LuoguP1637] 三元上升子序列
题解对于 ,考虑在它前面比它小的数的个数记为 ,在它后面比它打的数的个数记为 ,相乘累加到答案。 显然,离散化一下后可以用树状数组统计。 具体方法是离散化后,遍历数组时把当前元素的值当作下标,在该下标的位置上
2018.11.08
分块入门 分块入门
引言时隔很久过来填坑了。其实分块就是暴力,其本质仍是对维护信息的割裂与整合归一 线性分块在线性结构上维护信息,我们尝试用分块处理。这种分块将结构分割为连续的几段,在维护段内的信息再整合为要查询的信息。形式化地说,我们把长度为 的序
2018.10.01
2 / 2