早上7：30，我们来到了这与我们泉州第一中学有长达2个汉字的最长公共子序列的中山纪念中学。
上午
学算法和数据结构
1. Graham 扫描法
定义
是一个给定 n 个点，求这 n 个点所构成的凸包的算法
什么是凸包
凸多边形是指所有内角大小都在 [0,\pi] 范围内的 简单多边形。
在平面上能包含所有给定点的最小凸多边形叫做凸包。
实际上可以理解为用一个橡皮筋包含住所有给定点的形态。
性质：凸包用最小的周长围住了给定的所有点。
性质
Graham 扫描法的时间复杂度为 O(n\log n)，复杂度瓶颈在于对所有点排序。
过程
首先找到所有点中，纵坐标最小的一个点 P。根据凸包的定义我们知道，这个点一定在凸包上。然后将所有的点以相对于点 P 的极角大小为关键字进行排序。
我们考虑从点 P 出发，在凸包上逆时针走，那么我们经过的所有节点一定都是「左拐」的。形式化地说，对于凸包逆时针方向上任意连续经过的三个点 P_1, P_2, P_3，一定满足 \overrightarrow{P_1 P_2} \times \overrightarrow{P_2 P_3} \ge 0。
新建一个栈用于存储凸包的信息，先将 P 压入栈中，然后按照极角序依次尝试加入每一个点。如果进栈的点 P_0 和栈顶的两个点 P_1, P_2（其中 P_1 为栈顶）行进的方向「右拐」了，那么就弹出栈顶的 P_1，不断重复上述过程直至进栈的点与栈顶的两个点满足条件，或者栈中仅剩下一个元素，再将 P_0 压入栈中。
代码实现
模板题
P2742 [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包
2. 旋转卡壳
引入
旋转卡壳（Rotating Calipers，也称「旋转卡尺」）算法，在凸包算法的基础上，通过枚举凸包上某一条边的同时维护其他需要的点，能够在线性时间内求解如凸包直径、最小矩形覆盖等和凸包性质相关的问题。
求凸包直径
定义
给定 n 个点，求求所有点对之间的最长距离
例题
P1452 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G
过程
首先使用任何一种凸包算法求出给定所有点的凸包，有着最长距离的点对一定在凸包上。而由于凸包的形状，我们发现，逆时针地遍历凸包上的边，对于每条边都找到离这条边最远的点，那么这时随着边的转动，对应的最远点也在逆时针旋转，不会有反向的情况，这意味着我们可以在逆时针枚举凸包上的边时，记录并维护一个当前最远点，并不断计算、更新答案。
求出凸包后的数组自然地是按照逆时针旋转的顺序排列，不过要记得提前将最左下角的 1 节点补到数组最后，这样在挨个枚举边 (i,i+1) 时，才能把所有边都枚举到。
枚举过程中，对于每条边，都检查 j+1 和边 (i,i+1) 的距离是不是比 j 更大，如果是就将 j 加一，否则说明 j 是此边的最优点。判断点到边的距离大小时可以用叉积分别算出两个三角形的面积并直接比较。
代码实现
3. 可持久化权值线段树（主席树）
引入
先引入一道题目：给定 n 个整数构成的序列 a，将对于指定的闭区间 [l, r] 查询其区间内的第 k 小值。
P3834 【模板】可持久化线段树 2
一种可行的方案是：使用主席树。 主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第 k 小。
解释
我们分析一下，发现每次修改操作修改的点的个数是一样的。都只更改了 O(\log{n}) 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度。注意主席树不能使用堆式存储法，就是说不能用 x\times 2，x\times 2+1 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。
所以我们只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。
我们把问题简化一下：每次求 [1,r] 区间内的 k 小值。怎么做呢？只需要找到插入 r 时的根节点版本，然后用普通权值线段树（有的叫键值线段树/值域线段树）做就行了。
回到原问题——求 [l,r] 区间 k 小值。
我们可以发现，主席树统计的信息也满足这个性质。
所以如果需要得到 [l,r] 的统计信息，只需要用 [1,r] 的信息减去 [1,l – 1] 的信息就行了。
代码实现
4. 一种方便的数据结构——可并堆
例题
P11266 【模板】可并堆 2
思路
可以使用 pb_ds 库中的 priority_queue 来解决。
与标准库中的 priority_queue 相同，pb_ds 库中也实现了一个堆。不同的是，pd_ds 库中增加了删除和修改的操作。
下面介绍一下 priority_queue 的基本语法：
priority_queue 的头文件在 bits/extc++.h 中，但由于它不是一个标准 STL 库，还需要引用命名空间 __gnu_cxx。
priority_queue 定义声明方式：__gnu_pbds::priority_queue pq;
在本题中会用到一下的操作：
1. pq.push(x)：将数字 x 放入堆中。
2. pq.top()：返回堆顶的元素。
3. pq.erase(it)：将迭代器 it 从堆中消除。
4. pq1.join(pq2)：将 pq2 放入 pq1 中，同时清空 pq2。
5. pq.modify(it,x)：将堆中迭代器为 it 的值改为 x。
代码实现
