我一直觉得单调队列和斜率优化都是很难理解的东西，事实上我也确实理解了很久。去年省选集训的时候学过一次，没学会；今年NOIP集训的时候又做了一题，还是没什么感觉；NOIP完了，又做了几题单调队列，还是看题解的……还好今年省选集训的时候还是弄懂了。

其实斜率优化之所以和单调队列关系这么大，原因还是大部分题目斜率优化能保证决策的单调性，不要的就扔掉，所以就用了单调队列了。既然单调队列这么重要，所以今年开始练斜率优化的时候我就先打了几题单调队列。

参考资料

• 浅谈数形结合思想在信息学竞赛中的应用 - 周源
• 用单调性优化动态规划
• 1D1D动态规划优化初步

单调队列

单调队列就是一定要想清楚，到底我什么时候该把头扔掉（一般删头是因为不满足题目要求，或者不够优并且不会在后面变优），到底我把什么样的尾扔掉（尾都是备胎，一般扔掉是因为当前尾由于当前状态的出现而变得一文不值，连当备胎的机会都没有）。

另外还有一个非常严重的问题，就是先维护队尾还是先维护队头。这个得取决于具体的DP方程，如果当前决策能选到自己的话，那就得先维护队尾再维护队头，最后把头那个决策拿出来算DP值。

斜率优化

因为斜率不单调的斜率优化我还没做出来（o(╯□╰)o），所以先不讨论斜率不单调的斜率优化。

总的来说，斜率优化就是这样：求最小值，维护下凸壳；求最大值，维护上凸壳。画个图还是比较容易理解的。转化出xy以后就变成模板了。

入门的话，这篇还是写的不错的：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html

个人认为，其实树链剖分并不是一个复杂的算法或者数据结构，只是能把一棵树拆成链来处理而已，换一种说法，树链剖分只是xxx数据结构/算法在树上的推广，或者说，树链剖分只是把树hash到了几段连续的区间上。

因为这东西本身没有功能，具体功能都是靠具体数据结构实现的，所以复杂度就是O(logn * ??)。如果套上了线段树，就是 O(log^2 n)。如果套上了树套树，那就是O(log^3 n)。如果你用树链剖分和树套树写区间第k大，那就是O(log^4 n)。

另外，树链剖分具体实现的时候是给边重新编号还是给点重新编号，这得根据不同的题目而定，实现的时候要注意顶端那个编号能不能取。

对了，这东西可以顺便求LCA。比如说基于点的剖分，就是剖分到两个点都到同一条重链的时候，比较上端的那个点。

下面是一些例题：

最近学习了一种筛素数的方法，能够在 O(n) 的时间内完成。一开始不能理解其中的一句话，搜索了很久，大部分的结果都是一群人在csdn上面卖萌。现在终于理解了，记下来备忘。下面的内容不卖萌，但是也不严谨。

算法的实质

这个算法在1978年，由 David Gries 和 Jayadev Misra 在 Communication of the ACM上提出来，可以在ACM Digital Library看到，价格是 $15.00 。当然，我们只是学习用途，所以可以在谷歌上找找，比如说：A Linear Sieve Algorithm for Finding Prime Numbers。因为ACM的版权限制还是比较严格的，这里就不放上pdf，如果上面的链接不起作用请自行搜索。

这个算法的核心思想是：每一个合数可以被唯一地表示成它的一个最小质因子和另外一个数的乘积。证明略。

伪代码：

S = {2, ..., n}
for (p = 2; p*p <= n; p = next(S, p)):
    print p
    for (i = p; i*p <= n; i = next(S, i)):
        for (j = i*p; j <= n; j = j*p):
            S = S - {j}

next(S, i) is a function defined only for i ∈ S such that 
there is an integer larger than i in S; it yields the next 
larger integer in S. 

传说中的切糕（切蛋糕）！出题人的题解：http://hi.baidu.com/xh176233756/item/cac0c6f8f9f1ec19e3e3bd3d

其实比较麻烦的是求出每块多边形的面积，如果能做出来的话，这题只是再略微加上一个弓形。下面先讲一下求每块多边形面积的方法：求域法

求域

首先预处理，算出所有交点，然后每个点向它相邻（指有线相连）的所有点连边：

枚举每一条边(u, v)，找出以v为起点，和(v, u)相比逆时针转角最大的边，按那条边走过去。重复这个步骤，直到走到了最初的那个点。经过的边围成的域就是一个独立的块：

给定a[]，求一种划分方法，使得每段的和不大于M，并且每段的最大值的和最小。

这题是好题，一年内我做了三遍，前两遍都是看题解，不断的改程序，最后碰运气过的。第三遍终于是自己做出来的。

前两次看到题目中最大值最小，总是会想到二分去，第三次一想，不对，如果能验证答案的话那也能直接求出答案。所以这题的正解还是动规。

f[i] = min{ f[j] + max{a[j+1]..a[i]} } (sum[i]-sum[j] <= M)

朴素方程是O(n^2)的，下面考虑优化。

区间最大值，而且还有和的限制，显然RMQ不管用了，然而单调队列正好就是处理这种事情的。保存一个单调递减的单调队列，那么我们取出来队头就是区间的最大值了。

假设我们队列里面的元素x的位置和值分别是Q[x].pos和Q[x].value，那么对于当前的最优决策只能是：min{ f[Q[x-1].pos] + Q[x].value }，因为从Q[x-1].pos到i这一段的最大值都是Q[x].value。

如果要科学一点地解释的话，那就要证明：如果一个点k能成为最优决策，当且仅当a[k] > max{a[k+1]..a[i]}。原因也很简单，如果a[k]不比后面的值大的话，那么我们不如在k前面找一个x，使得max{a[x+1]..a[i]} = max{a[k+1]..a[i]}，又因为人类已经无法阻挡f[i]递增的趋势了，注意看DP方程，会发现f[x] <= f[k]，而后面那项又是相等的，所以k肯定不如x优。

下面我们该考虑如何得到最优决策，毕竟我们只是保证了队列里面的数是递减的，只是去掉了一些无用的决策，还是得对队列里面的每个元素计算 min{ f[Q[x-1].pos] + Q[x].value }。容易发现，这个值插进队列里面以后是固定的（跟i无关），所以随便拿一种O(log n)的数据结构都可以维护这个的最大值。一般人回去打平衡树，我比较喜欢线段树，所以就用队列下标建了一棵线段树。另外堆也是可以的，如果用一个bool数组表示当前值是否被删，然后配合std::priority_queue<>也是可以搞的（就跟Dijkstra + Heap一样）。

程序如下：

计算区间内的素数，区间的起始点和终止点可能很大（2^{31），但是区间长度很小（10}6）。这题是筛素数的经典应用。

求恰好被覆盖k次的圆面积并。

如果做过圆面积并（[SPOJ CIRU]The area of the union of circles）的话，那么这题就比较简单了。参考：。主要的区别就是：

• 原先做线段覆盖，现在改为括号匹配（压栈）。原先计算没被覆盖的面积，现在计算至少覆盖k+1次的面积area[k+1]，答案就是area[k]-area[k+1]。
• 如果一个圆被完全包含，原先直接扔掉，现在要加上去。

代码基本不变：

AC大神写过一篇圆面积并的文章，好像大家都是从他那边学来的（吐槽一下百度，自家空间的内容搜不到，但是谷歌就可以）：求圆并的若干种算法,圆并扩展算法

首先，如果做过圆周长并（[BZOJ1043][HAOI2008]下落的圆盘）的话，那做圆面积并就简单了。

根据AC大神的理论，圆的面积并的结果就是一大堆弓形+一个凸多边形（如果所有圆都交在一个块的话）。因此算面积并的话，就只要算出所有弓形的面积（1/2 * R * R * (α - sin(α))），还有所有有向线段的有向面积即可。所有的弓形其实就是每个圆没被覆盖的部分，这个比较好求。但是那个多边形呢？

AC大神提出了一种很厉害的方法：对于每个圆，枚举所有和它相交的圆，然后记下所有相交的区间，剩下的区间（若干条弧），计算弧所对应的弓形还有弧所对应的有向线段的有向面积。

如图，当前圆为圆A，绿色和蓝色部分为当前圆没被覆盖的部分，而且一定是圆并中仅被覆盖一次的面积！实际上我们算的只有弧FG 弧GI和向量FG 向量HI的面积，因为其他几条线段被包含在多边形EFGHI里面了，而且这个多边形的每条边都会被算到一次且仅一次。

然后有一种特殊情况：

中间那块多边形明显是不算面积的，但是似乎是算了两次？如何解决BUG？

实际上这根本没有BUG，中间那块面积是负数！因为中间的有向线段方向是相反的！

所以这题就这样就可以做掉了（基本上就是圆周长并改一改）。代码也不长：

题意

给定一个n个点n条边的有向图，其中每个点都只有一条出边，然后添上每条边的反向边（也就是原地变成无向图），问在每个点都只经过一次的情况下，最长的路程是多少。

分析

首先分析一下n个点n条边的图会是什么样的。去掉一条边比较好想，要么一棵树，要么若干棵个环+一棵树。那么把这条边加上去，这条边显然只能让一棵树产生一个环，或者是连接一棵树和一个环，不可能连接两个环（因为每个点只有一条出边，组成环必然用完了每个点的出边）。总的是来说，这一张图就是：若干个连通分量，并且每个联通分量里面只能是一个中心环+若干棵外向树。

我们对于每个联通分量单独考虑，然后再把每个联通分量里面的最长路径加起来就是答案了（因为题目说岛之间是坐船，不算在行走路程里面）。

现在我们的问题是：对于一个环+若干个外向树，如何求出最远距离？

显然最远距离不可能是在环上，因为可以向外向树延伸，让路径变得更长。所以答案仅有下面两种可能性：

• 两端在某一棵外向树上
• 一端在某一棵外向树上，然后走了环的一部分，最终到达另外一棵外向树

第一种只要对于每一棵外向树计算出最远距离就好了。我们来考虑一下如何计算第二种的答案。

这题就是经典的圆周长并（实际上周长并指的是覆盖，不然的话，- -||）。算是比较水的题目。

首先，这题的n不是很大，我们可以得到一个非常朴素的O(n^2)的方法：对于每个圆，枚举它后面掉下来的所有的圆，然后计算没被覆盖的部分。我们可以发现，对于一个圆，如果以它为原点建立极坐标系，每个圆覆盖它的部分都是一段连续的弧度区间。如果把所有的区间求出来了，那么剩下的问题就是经典的线段覆盖问题了。

我们来看一下这个覆盖区间怎么求。

如图，用绿色和蓝色标出来的两个角度我们都可以求出来：绿色的是atan2(A.y-O.y, B.x-O.x)，蓝色的可以通过△AED上的余弦定理算出来。为什么绿色的不用余弦定理呢？因为余弦定理的角只能是[0, pi]，根本无法分清A在O的上方还是下方（这个地方我被坑了）。

为了方便做线段覆盖，最好还是把角度区间统一一下，比如全部变成[0, 2pi]。这个时候就要注意，如果有跨过2pi的区间，要拆成两部分。

代码还是比较短的：