势能分析
定义
对于每次操作，
常见势能分析
势能为连续段的个数
简要题意：现在有一个长度为 $n$ 的数列 $a_i$，初始时，每个位置的值都是 $0$，颜色为 $1$，现在有 $m$ 个操作，操作有三种：给定区间 $[l,r]$ 和颜色 $c$，将区间 $[l,r]$ 染成 $c$；给定颜色 $c$ 和值 $x$，将所有颜色为 $c$ 的位置的值增加 $x$；给定位置 $i$，求 $a_i$
$n,m\le 10^6$
简要题解：我们考虑用线段树维护区间连续段，同时全局维护加标记，这样二操作可以直接修改全局标记，一操作我们注意到如果区间颜色都相同可以直接打标记，那么如果区间颜色相同我们打标记，否则我们暴力向下递归修改
我们考虑使用势能分析证明这样操作的时间复杂度，我们定义势能为区间连续段的个数，注意到一操作至多使连续段的个数增加 $2$，从而得到 $\phi(n)=O(n)$，同时一操作的势能代价函数 $f(x)=x\log n$，所以总的时间复杂度为 $f(\phi(n))=O(n\log n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，操作分两种，每次操作给定三个整数 $l,r,k$，第一种操作是将给定 $[l,r]$ 的数字都置为 $k$，第二种是查询区间 $[l,r]$ 的第 $k$ 小数
$n,m\le 10^5,1\le a_i,k\le 10^9$
简要题解：通过上题的势能分析，我们可以得到一操作得到的所有区间的数量为 $O(n\log n)$，拿到这些区间可以直接套整体二分的板子
简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有两种，给定 $l,r$ 区间中每个 $a_i$ 变成 $\sqrt{\lfloor a_i\rfloor}$；给定 $l,r$，区间中每个数 $a_i$ 变成 $a_i^2$，在所有操作进行完之后，请输出 $\sum_{i=1}^na_i$
$n,m\le 2\times 10^5$
简要题解：注意到平方后再开根相当于没进行平方，而开方后在平方则不行
我们对于线段树上每个点维护平方了多少次，区间开方时，区间内每个点都至少平方了一次，则可以直接做区间减，否则我们暴力进行开方，注意到每个数最多被开 $O(\log\log n)$ 就会变成 $1$，时间复杂度 $O(n\log n\log\log n)$