【算法介绍】二维数点
算法简介:一箭双丘丘!其实吧,二维数点单独来讲不能算是一个算法,它泛指一种在二维平面上数有多少个点或类似的问题。涉及的数据结构比较广,也算是比较杂的一篇文章了。
二维数点大概有两种:静态的和动态的。根据题目给出的动静之分,我们可以大致知道用什么数据结构,一般来讲,单点动态的我们偏向用树状数组等操作,多点动态应该除了线段树没谁了;还有就是静态,一般来讲非必要情况都是树状数组,毕竟码量低,然后有时候会有扫描线的题目。扫描线还没讲,先挖个坑罢(
这里就挑几个二维数点的实例看看,大概意会一下。
算法演示:一触即发例题一:烧起来啦!大秦为你打开题目传送门
题面翻译平面上有n个点,还有一个长度为⑨的数列$a_1,a_2……a_9$满足$\sum_{i=1}^na_i=n $
你需要画两条水平直线和两条竖直直线将平面划为⑨各部分,每部分点数记为$b_1,b_2……b_9$
要求b是a的一种排列
你的直线坐标可以是实数,构造一组解,或无解(输出-1)
题目思路虽然说他是紫题,但是太简单了,不必有任何压力(我是一眼秒的
让你把一堆点分成一个九宫格(其实是找九宫格中间的四条分界线)然后每一个格子一定是给 ...
【拾题杂谈】LuoguP2486 [SDOI2011] 染色
题面:[SDOI2011] 染色题目描述给定一棵 $n$ 个节点的无根树,共有 $m$ 个操作,操作分为两种:
将节点 $a$ 到节点 $b$ 的路径上的所有点(包括 $a$ 和 $b$)都染成颜色 $c$。
询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。
颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成:11、222、1。
输入格式输入的第一行是用空格隔开的两个整数,分别代表树的节点个数 $n$ 和操作个数 $m$。
第二行有 $n$ 个用空格隔开的整数,第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。
第 $3$ 到第 $(n + 1)$ 行,每行两个用空格隔开的整数 $u, v$,代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。
第 $(n + 2)$ 到第 $(n + m + 1)$ 行,每行描述一个操作,其格式为:
每行首先有一个字符 $op$,代表本次操作的类型。
若 $op$ 为 C,则代表本次操作是一次染色操作,在一个空格后有三个用空格隔开的整数 $a, b, c$,代表将 $a$ 到 $b$ 的路径上 ...
【拾题杂谈】LuoguP2590 [ZJOI2008] 树的统计
题面:[ZJOI2008] 树的统计大秦为你打开题目传送门
题目描述一棵树上有 $n$ 个节点,编号分别为 $1$ 到 $n$,每个节点都有一个权值 $w$。
我们将以下面的形式来要求你对这棵树完成一些操作:
I. CHANGE u t : 把结点 $u$ 的权值改为 $t$。
II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。
III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。
注意:从点 $u$ 到点 $v$ 的路径上的节点包括 $u$ 和 $v$ 本身。
输入格式输入文件的第一行为一个整数 $n$,表示节点的个数。
接下来 $n-1$ 行,每行 $2$ 个整数 $a$ 和 $b$,表示节点 $a$ 和节点 $b$ 之间有一条边相连。
接下来一行 $n$ 个整数,第 $i$ 个整数 $w_i$ 表示节点 $i$ 的权值。
接下来 $1$ 行,为一个整数 $q$,表示操作的总数。
接下来 $q$ 行,每行一个操作,以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。
输出格式对 ...
【拾题杂谈】LuoguP3384 【模板】重链剖分/树链剖分
题面:【模板】重链剖分/树链剖分大秦为你打开题目传送门
题目描述如题,已知一棵包含 $N$ 个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:
1 x y z,表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
2 x y,表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
3 x z,表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
4 x 表示求以 $x$ 为根节点的子树内所有节点值之和
输入格式第一行包含 $4$ 个正整数 $N,M,R,P$,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。
接下来一行包含 $N$ 个非负整数,分别依次表示各个节点上初始的数值。
接下来 $N-1$ 行每行包含两个整数 $x,y$,表示点 $x$ 和点 $y$ 之间连有一条边(保证无环且连通)。
接下来 $M$ 行每行包含若干个正整数,每行表示一个操作。
输出格式输出包含若干行,分别依次表示每个操作 $2$ 或操作 $4$ 所得的结果(对 $P$ 取模)。
样例 #1样例输入 #11 ...
【算法介绍】树链剖分
算法简介:空取奇思的手艺接下来的内容是关于链剖分的,没错,就是链剖分,那个每次去和线段树凑在一起用的算法,其实线段树早就已经讲过很久了,这个链剖分着实讲的有点晚,不过无伤大雅,这次讲清楚便是。
友情链接:
【算法介绍】普通线段树 | 祝馀宫【算法介绍】线段树合并 | 祝馀宫
链剖分大概分为三个主流的:
树链剖分(也叫重链剖分)
实链剖分(就是熟知的恶魔 LCT )
长链剖分(和重链剖分齐名的一种剖分方式)
这一篇的内容就是关于重链剖分的,后续可能会接着把几个连剖都搞完。
算法演示:巧言贴耳的诱引算法推导:玄迷灵敏的指法首先,重链剖分其实是非常形象的。他的名字:重链剖分的重,直接表明了他的主要思路,通过轻重儿子剖分。所谓轻重儿子,我们把一个节点 $u$ 的儿子中,子树(包含那个儿子)的大小中最大的,就是重儿子,记作 son[u] ,S也就是 $u$ 的重儿子。( sz[u] 表示以 $u$ 为根的子树大小)
sz[son[u]] = \max_{v\ \in\ \operatorname{child}(u)} sz[v]那么什么叫做以轻重儿子剖分呢?我们在定义下面的内容,父亲连 ...
【奇技淫巧】特殊思维题的复杂度分析
算法简介:堆叠真空域在做题的过程中,我们经常会发现那些看上去是纯暴力,但是复杂度却是 $n\log n$ 或者其他的算法或思想。这些题抓住了做题人在计算复杂度时候的失误,从而达到了思维难度提升的效果。他们通常题目评级不高,但是却总是很难想到。
算法演示:不羁型贝特大致思想:零失误少女这类题目有一大特点:倍增
比如说这些题目 P9974【USACO23DEC】Candy Cane Feast B 、【ABC315F】Shortcuts 等等等等,他们的题目或多或少都点到了一个关键字二的幂次、翻倍。比如说 USACO 的这道,虽然没有直接提到翻倍,但是我们会注意到奶牛最多吃到和自己一样高的糖果,也就是说第一只奶牛会一直翻倍,这也保证了复杂度。
这样倍增的性质,通常是隐蔽的,有些甚至感觉微小的不可发现,这也是成就了这些题目难度的主要因素。而这种倍增是丰富多样的,比如说刚刚给出的第二题,跳过的代价显而易见是极高的,我们发现最大距离会远小于跳过多个点,更具这个性质,我们可以把题目的空间以及时间复杂度压到 $\log n$ 。这是一种倍增代价,去发现优劣的思路。
除此之外,比如说启发式合并,每次合 ...
【拾题杂谈】[USACO24OPEN] Farmer John’s Favorite Permutation B
题面:FJ’s Favorite Permutation B题目描述Farmer John 有一个长为 $N$($2\le N\le 10^5$)的排列 $p$,包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而,Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍,FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时,FN 会执行以下操作:
令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$,
如果 $p_1^\prime>p_n^\prime$,他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。
否则,他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。
最终,Farmer Nhoj 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$,Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$,或者判断 ...
【拾题杂谈】LuoguP11261 [COTS 2018] 直方图 Histogram
题面:[COTS 2018] 直方图 Histogram题目背景译自 Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,1G}$。
题目描述给定笛卡尔坐标系中的直方图,宽度为 $n$,第 $i$ 格的高度为 $h_i$。也就是说,对于 $\forall 1\le i\le n$,第 $i$ 格所占矩形的顶点坐标分别为 $(i-1,0),(i,0),(i-1,h_i),(i,h_i)$。
给定正整数 $p$,求出满足以下条件的矩形的数量:
矩形的四个顶点的坐标均为整数;
矩形有一条边在 $x$ 轴上;
矩形完全位于直方图内部(可以与边界相切);
矩形的面积至少为 $p$。
输入格式第一行,两个正整数 $n,p$。
第二行,$n$ 个正整数 $h_1,h_2,\ldots,h_n$。
输出格式输出一行一个整数,表示答案。
样例 #1样例输入 #1126 91 4 4 5 2 3
样例输出 #113
样例 #2样例输入 #21210 53 6 1 3 2 1 5 3 4 2
样例输出 #21 ...
【拾题杂谈】LuoguP1377 [TJOI2011] 树的序
题面:[TJOI2011] 树的序题目描述众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:
空树中加入一个键值 $k$,则变为只有一个结点的二叉查找树,此结点的键值即为 $k$。
在非空树中插入一个键值 $k$,若 $k$ 小于其根的键值,则在其左子树中插入 $k$,否则在其右子树中插入 $k$。
我们将一棵二叉查找树的键值插入序列称为树的生成序列,现给出一个生成序列,求与其生成同样二叉查找树的所有生成序列中字典序最小的那个,其中,字典序关系是指对两个长度同为 $n$ 的生成序列,先比较第一个插入键值,再比较第二个,依此类推。
输入格式第一行,一个整数 $n$,表示二叉查找树的结点个数。第二行,有 $n$ 个正整数 $k_1, k_2, \cdots,k_n$,表示生成序列,简单起见,$k_1 \sim k_n$ 为一个 $1$ 到 $n$ 的排列。
输出格式一行,$n$ 个正整数,为能够生成同样二叉查找树的所有生成序列中最小的。
样例 #1样例输入 #11241 3 4 2
样例输出 #111 3 2 4
提示数据范围及约定
对于 $20\%$ 的数据, $1\l ...
【算法介绍】笛卡尔树
算法简介:林雾间的行迹上次的图论差不多研究完了,这次就打算开一个新的专题。本来是想着动态规划来着,正巧有一个什么活动,让我们整一个笛卡尔树的算法学习笔记,那我就略略研究了一下,写下来的专题不出意外我都会写一些树状树形结构,尤其是二叉搜索树这一类的,可以去看博客里的二叉搜索树标签。(马上要 noip 了,更新不会太快)
刚刚也说了,笛卡尔树其实是一种二叉搜索树的结构,二叉搜索树的概念还没有讲过,估摸着后面会和平衡树的时候一起系统的介绍。而笛卡尔树作为二叉搜索树的一个分支内容,自然是有着二叉搜索树的特殊性质,我们的副标题也提到他是二叉搜索树中的小根堆,这是为什么呢?且听下文分解。
算法演示:藏蜜酒的王蜂基本概念:栖地蝠的灵笼首先我们要讲笛卡尔树,来先讲讲二叉搜索树的基本概念。所谓二叉搜索树,就是对于这棵树上所有的节点,他的左子树的所有节点都小于该节点,他的右子树中的所有点都大于该节点。特殊的,空树也是一个二叉搜索树。
举一个二叉搜索树的例子:
显而易见的,这是一个非常规范的二叉搜索树。这里给出一个二叉搜索树的可视化生成网站,可以更加直观的理解二叉搜索树。我们可以先模拟一下二叉搜索树的过程 ...