【算法介绍】二维数点
算法简介：一箭双丘丘！其实吧，二维数点单独来讲不能算是一个算法，它泛指一种在二维平面上数有多少个点或类似的问题。涉及的数据结构比较广，也算是比较杂的一篇文章了。
二维数点大概有两种：静态的和动态的。根据题目给出的动静之分，我们可以大致知道用什么数据结构，一般来讲，单点动态的我们偏向用树状数组等操作，多点动态应该除了线段树没谁了；还有就是静态，一般来讲非必要情况都是树状数组，毕竟码量低，然后有时候会有扫描线的题目。扫描线还没讲，先挖个坑罢（
这里就挑几个二维数点的实例看看，大概意会一下。
算法演示：一触即发例题一：烧起来啦！大秦为你打开题目传送门
题面翻译平面上有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 了，更新不会太快）
刚刚也说了，笛卡尔树其实是一种二叉搜索树的结构，二叉搜索树的概念还没有讲过，估摸着后面会和平衡树的时候一起系统的介绍。而笛卡尔树作为二叉搜索树的一个分支内容，自然是有着二叉搜索树的特殊性质，我们的副标题也提到他是二叉搜索树中的小根堆，这是为什么呢？且听下文分解。
算法演示：藏蜜酒的王蜂基本概念：栖地蝠的灵笼首先我们要讲笛卡尔树，来先讲讲二叉搜索树的基本概念。所谓二叉搜索树，就是对于这棵树上所有的节点，他的左子树的所有节点都小于该节点，他的右子树中的所有点都大于该节点。特殊的，空树也是一个二叉搜索树。
举一个二叉搜索树的例子：
显而易见的，这是一个非常规范的二叉搜索树。这里给出一个二叉搜索树的可视化生成网站，可以更加直观的理解二叉搜索树。我们可以先模拟一下二叉搜索树的过程 ...
