势能分析法，是时间复杂度分析中用来分析摊还时间复杂度的一种方法。摊还时间复杂度，即将用时长的操作均摊到用时短的操作上面。如果一个数据结构它有一些操作的用时很长，但是有一些操作的用时很短，就可以使用均摊时间复杂度来描述它的时间复杂度。我们认为，用时长的操作所花的时间可以均摊到用时短的操作所花的时间上面。

前置知识：单调队列（可以在题解处学习）

在单调队列里面，包含很多入队操作和一些出队操作。时间复杂度为 $\Theta(n)$ 的标准解释是一个元素最多入队和出队一次，这个解释很清晰，但是本文讲的是势能分析法不是神仙分析法，所以下面将用势能分析来分析其时间复杂度，同时作为引入。

令势能函数 $\Phi(S)=\text{S中元素个数}$。其中 $S$ 代指单调队列的整个数据结构。对于任意单调队列，我们都可以计算出它的势能函数对应的值。例如，有三个元素为 1 3 5 的单调队列 $S_1$，其势能函数 $\Phi(S_1)=3$。

以下假设将单调队列的 push 拆分为弹出（即那个 while 循环）和 入队（弹出后的入队）。

容易得知：

所以我们就可以将弹出操作弹出元素时 head-- 和一次判断的开销摊到入队操作上。因为每次弹出一个元素，势能函数就会 -1。而在入队操作的时候，势能函数 +1。

有一篇英语阅读（完形填空），讲的是一个咖啡馆的故事。一些顾客买咖啡，会额外买一杯咖啡 for wall ，然后服务员会贴一张纸条到墙上。当一个衣衫褴褛的流浪汉买咖啡时，他可以买一杯咖啡 from wall ，服务员就会从墙上揭下一张纸条，然后提供给流浪汉一杯免费咖啡。势能函数就可以理解成这个故事里的 wall 。实际花费是顾客或流浪汉实际得到的咖啡，而均摊后的花费是顾客或流浪汉为这杯咖啡所付的钱。

由于每次 while 的开销都会使墙上的订单减少 1，而单次入队操作只会使墙上的订单增加 1，所以我们可以认为每次弹出和入队所花的钱都是一个常量。用势能分析的语言说，while 的开销可以由势能支付。由于柜台一分钱都没有亏，所以我们卖出的咖啡喝收到的钱一样多，所以每次弹出和入队所花的时间就可以认为是一个常量。

因此，每次弹出和入队的时间复杂度都是 $\Theta(1)$，出队的时间复杂度显然也是 $\Theta(1)$，则总时间复杂度是 $\Theta(n)$。

这里单调队列的算法时间有一个 for 套一个 while，虽然表面上是双重循环 $\Theta(n^2)$ 的，但是最终却可以证明是 $\Theta(n)$ 卡不掉的时间复杂度。这就是摊还时间复杂度的魅力。

例题：P1840 Color the Axis，本节将证明一个看似乱搞算法的时间复杂度是 $\Theta((n+m)\alpha(n))$ 的。

附题面简述

有一个长度为 $n$ 的序列，开始全 1，有 $m$ 个操作，每次将一个区间赋为 $0$，求每次操作后 $1$ 的数量。

这题标准解法应该是线段树区间赋值+查询，能够达到 $\Theta(m\log n)$ 的时间复杂度。

但是线段树的题怎么能用线段树做呢。我当即拍了一个暴力解，每次循环赋 0。这个算法稳 $\Theta(nm)$，肯定炸。所以我就用并查集维护一些已经赋为 0 的段，并查集的代表元素选为段的最末尾一个元素，每次直接 getfa(l) 跳到段尾，然后合并来表示赋 0。

（参见题解里面某位 dalao 的解法，我这个菜鸡竟然和 dalao 想到一块了）

然后就 458ms AC。

我：？？？这不是 $\Theta(nm)$ 加优化吗？？？

然后我想了一会，口糊出了一个时间复杂度为 $\Theta((n+m)\alpha(n))$ 的证明。

首先，定义一个势能函数 $\Phi(S)=\text{S中不同的集合的个数}\times\alpha(n)$。S表示维护这个区间的并查集。

算法开始时，并查集有 n 个不同的集合，所以算法开始时的势能函数 $\Phi(S)=n\alpha(n)$ 。

而每次操作的时候，每次 while 循环中要执行两个步骤：

这两个步骤中的步骤 2 会使势能函数减少 $\alpha(n)$ ，刚好弥补第一个操作 $\Theta(\alpha(n))$ 的开销。所以，我们可以认为每次操作的 while 循环内部的耗时由势能支付。

所以，每次操作只需要负担最开始的 l=getfa(l) 的 $\Theta(\alpha(n))$ 的开销。由于一开始势能函数为 $\Theta(n\alpha(n))$，最终时间复杂度即为 $\Theta((n+m)\alpha(n))$。

在实际做题的时候，可以忽略 $\alpha(n)$，而认为其时间复杂度就是 $\Theta(n+m)$。

前置知识：Splay

学习完 Splay，许多人都会有一个疑惑：为啥这么旋就能让均摊时间复杂度变成 $\Theta(n\log n)$。毕竟，旋转操作好像并没有把树平衡多少。

这里就要证明 Splay 访问一个节点并将其调整到根的开销为 $\Theta(\log n)$。

对于一个节点 $t$，定义势能函数 $\Phi(t)=\log \text{siz[t]}$，其中 $\text{siz[t]}$ 表示以 $t$ 为子树的 Splay 的大小。对于一个 Splay（命名为 $S$)，定义其势能函数为 $\Phi(S)=\sum\limits_{x\in S}\Phi(x)$。很显然，对于任意 $n$ 次插入操作，最终势能 $\Phi(t_n)$ 减去初始势能 $\Phi(t_0)$ 是 $\Theta(n\log n)$ 级别的，即用于升高势能的总花费是 $\Theta(n\log n)$ 的，则只需要证明旋转操作所需的时间为 $\Theta(\log n)$ 就好。

这里需要分类讨论。

（图源网络，侵权删）

这里，我们定义旋转前 $p$ 为 $x$ 的父亲，旋转的时候旋转 $x$，即与左图中相应字符标注的节点所处的位置对应。旋转后 $p$ 节点旋转成 $p'$，$x$ 节点旋转成 $x'$，即与右图中相应字符标注的节点的位置对应。不失一般性的，我们认为左边是旋转前，右边是旋转后。

容易看出，因为这个旋转并没有影响到 A、B 和 C子树里的所有点的权值，$\Delta\Phi(S) = \Phi(x')+\Phi(p')-\Phi(x)-\Phi(p)$（注意，等式右边为整个 Splay 的势能，右边为单点势能）。由于 $\Phi(x')=\Phi(p)$（它们的大小相等），因此 $\Delta\Phi(S) = \Phi(x')-\Phi(p)+\Phi(p')-\Phi(x)=\Phi(p')-\Phi(x)\text{siz[p']}$，所以上式可以写成 $\Delta\Phi(S)=\Phi(p')+\Phi(g')-\Phi(x)-\Phi(p)a+b$

由于对数函数单调递增（函数值随x的增大而增大），所以可以得到：

$$\log(\frac{ab}{c^2}) \text{siz[x]}+\text{siz[g']}$ 并不一定成立。所以，不能草率地认为“完全一样”。

但是，相差也并不大。读者可以自己试着推一下加深理解。详细过程在第六节给出。

将之前所有求得的不等式累加起来。由于 2 节推出的不等式式的差分系数为3，所以可以将第一个单旋的系数也化为 3，可以证明 $\Theta(1)+(\Phi(x')-\Phi(x))0$，总是可以找到一对 $i,k$ 令 $rnk(fa(x))\geq A_k^i(rnk(x))$，而 $level(x)=\max(k)$，在这个前提下，$iter(x)=\max(i)$。$level$ 描述了 $A$ 的最大迭代级数，而 $iter$ 描述了在最大迭代级数时的最大迭代次数。

对于这两个函数，$level(x)$ 总是随着操作的进行而增加或不变，如果 $level(x)$ 不增加，$iter(x)$ 也只会增加或不变。并且，它们总是满足以下两个不等式：

$$0\leq level(x)='0' && c