【基础语法】第一篇之 “读入输出”
基础语法之“读入输出”
基本介绍在 C++ 读入有两种流派，第一种是 C++ 新出品的 cin/cout 代表的 IOS 流派。第二种是传承自 C 语言的 scanf/printf 代表的旧语法流派。当然还有一些人会使用 快读/快写 等高速读入方式，后面的文章会提及。
IOS 流派
读入
一般来讲，在新手入门时，推荐使用$cin$来读入，其格式类似于：
123456789#include<bits/stdsc++.h>#include<iostream>// iostream 是包含 cin/cout 的头文件，当然包括在万能头里，所以如果引用了万能头，就不必担心用不了 cin/cout 了using namespace std;// 另外，cin/cout 还依赖于 C++ 新出的 std 库，也就是说我们必须引用 std 命名空间才可以，就是上面那一句话，不然的话我们要在所有和 std 有关的工具前面加上 std:: 这是命名空间的引用方式，以后的文章也会提及，举个例子，如果没有引用 std 库，那么 cin/cout 会变成 std::cin/std: ...
【算法介绍】扫描线思想
算法简介：号 · 仙蕊玲珑这篇文章就是继二维数点里挖下的坑的扫描线内容了。对于扫描线问题，其实是非常广泛的，就像动态规划一样。他主要是提供了一个在二维平面上用平行于坐标轴的线一个一个扫描过来的思想。总归一句话：只有你想不到，没有你扫不到。
友情链接：
【算法介绍】二维数点 | 祝馀宫
只要你可以按照题目的意思建立出可以通过题目的坐标系和线段，使其可以用扫描线扫出来，那么它就是可以的！
算法思想：武 · 西风长枪首先，既然叫做扫描线，那么上面叫做扫描呢？顾名思义，扫描扫描，从下到上扫一遍就可以了，但是扫描线其实还有一个特点，扫描线。其实所谓扫描线思想，就是把问题转化成一些线段，去按照某个顺序扫描他，然后顺便处理出问题。
我们可以先给出一个扫描线的经典问题，求矩形面积并。所谓矩形面积并，就是一堆矩形叠在一起，重复覆盖的地方只算一次，当然只出现一次的也是算一次（
那么这题首先第一眼应该都是暴力，毕竟大家都没什么好的思路去做这样奇怪的题目，那么，如果是扫描线呢？他其实是可以做出这样的题目的。为什么，我们来想想矩形是什么。小学大家就学过老师的名言：点动成线，线动成面。其实矩形的本质，就是一个 ...
【算法介绍】二维数点
算法简介：一箭双丘丘！其实吧，二维数点单独来讲不能算是一个算法，它泛指一种在二维平面上数有多少个点或类似的问题。涉及的数据结构比较广，也算是比较杂的一篇文章了。
二维数点大概有两种：静态的和动态的。根据题目给出的动静之分，我们可以大致知道用什么数据结构，一般来讲，单点动态的我们偏向用树状数组等操作，多点动态应该除了线段树没谁了；还有就是静态，一般来讲非必要情况都是树状数组，毕竟码量低，然后有时候会有扫描线的题目。扫描线还没讲，先挖个坑罢（
这里就挑几个二维数点的实例看看，大概意会一下。
算法演示：一触即发例题一：烧起来啦！大秦为你打开题目传送门
题面翻译平面上有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 ...
