简介
大概像是一种 $dp$ ?
反悔贪心的特点是每次决策都能会至少选一个东西，同时反悔贪心像 $dp$ 一样，一定能保证任意时刻都是最优的
反悔堆
对于一系列在限制中选择若干物品使得价值最大的问题中比较适用
常见情况：选择每个物品有代价 $w$，能获得价值 $c$，同时还有一个限制，限制的条件与已经选择的物品的代价有关，一般情况下，所有物品要么代价都是 $1$，要么价值都是 $1$，要不然不能进行替换
常见处理方法：
按照限制排序，然后进行反悔贪心，用堆维护物品的代价和价值，因为一定有一项为 $1$，所以堆的大小为一项，堆内元素为另一项
正确性：
我们将其看成一个类似于 $dp$ 的东西，在选择第 $i$ 个物品之后，相当于我们已经求得前 $i$ 个物品选择的最大价值，然后我们向 $i+1$ 转移，只不过这个转移不是用的一般 $dp$ 的转移方法
在这类题目的限制中，我们一般是使用当前物品去替换已经选择的物品，注意到被扔出来的物品一般不会回归，原因是堆中的物品的代价或价值随着时间进行是越来越优的
或者我们再换几种说法
例题
简要题意：现在有 $n$ 个建筑需要修复，修复第 $i$ 个建筑需要 $t_i$ 秒，第 $i$ 个建筑需要在 $d_i$ 秒内进行修复才有效，求最多能修复多少建筑
$n\le 1.5\times 10^5$
简要题意：每个物品价值为 $1$，代价为 $w_i$，限制为当前所选物品的代价和不能超过 $h_i$
因为所有建筑价值都相同，所以将建筑按照限制时间 $t_i$ 进行排序，用大根堆维护已经选的建筑，如果当前建筑不能选，则尝试去替换之前某一个耗时比它的大的建筑，时间复杂度 $O(n\log n)$
简要题意：现在有 $n$ 个工作可以完成，完成每个工作需要 $1$ 的时间，完成第 $i$ 个工作可以获得 $c_i$ 的收益，第 $i$ 个工作的截止时间是 $d_i$，求最大获利
$n\le 10^5$
简要题解：每个物品价值为 $c_i$，代价为 $1$，限制为当前所选物品的代价和不能超过 $h_i$
由于所有工作的完成时间相同，所以我们将所有工作按照截止时间排序，用小根堆维护已经选的工作，如果当前工作无法完成，就去替换一个收益最小的工作，时间复杂度 $O(n\log n)$
简要题意：$x$ 轴上有 $n$ 个位置，第 $i$ 个位置的坐标为 $x_i$，初始时你位于 $0$，从 $x$ 走到 $y$ 需要花 $|x-y|$ 的时间，在第 $i$ 个位置，可以花 $t_i$ 的时间得到这个位置的收益（只能得到一次），每个位置的收益都是 $1$，现在你只有 $m$ 的时间，求最大收益
$n,m\le 10^5$
简要题解：首先肯定不会向回走，那么我们枚举走到的最远的位置来计算答案即可，另外观察到收益全部相同，我们考虑反悔贪心
用大根堆维护所选的位置，如果不能到达第 $i$ 个位置，就依次从大根堆中 $pop$ 直到能够到达第 $i$ 个位置，然后如果我们能获得第 $i$ 个位置的收益，我们就直接获得并将其扔进大根堆中，否则就尝试替换花费时间最多位置
时间复杂度 $O(n\log n)$
简要题意：你现在有一个数 $x$，初始为 $0$，接下来 $n$ 分钟，每分钟可以将其加上 $[-k,k]$，同时需要保证每分钟结束时 $x\le a_i$，令 $b_i$ 为第 $i$ 分钟结束时的数，现在有一个长度为 $n$ 的序列 $w_i$，最大化 $\sum_{i=1}^nb_iw_i$
$n\le 10^6$
简要题解：首先我们将 $w$ 转换为后缀，那么如果在第 $i$ 步加了 $k$，那么会对总收益造成 $k\times suf_i$ 的影响，这样就能将每一步的贡献独立出来，那么现在唯一的限制就是前缀，注意到每个物品的代价本质是一样的（我们将每个物品拆成 $2k$ 个即可），我们考虑反悔贪心，令 $c_i$ 为物品的价值
注意到因为代价只有上界限制，所以我们使用以 $c$ 排序的大根堆，堆里同时存储 $c$ 和可以撤回的量
对于 $c>0$ 的物品，我们直接花代价 $k$ 来获得最大价值，然后扔到堆里
对于 $c<0$ 的物品，我们直接花代价 $-k$ 来获得最大价值
然后如果超出限制，我们再通过反悔贪心来减少某些位置的选择
简要题意：给定一个长度为 $n$ 的序列 $a_i$，要求选出最长的一个子序列，满足这个子序列的任意前缀非负
$n\le 2\times 10^5$
简要题解：注意到限制只有下界限制，所以所有非负数一定选，对于一个负数，能选则选，否则按照最传统的反悔贪心的做法即可，时间复杂度 $O(n\log n)$
反悔自动机
一般反悔自动机的题目确定正确性的方法都是我们能够确定最优的情况一定是能够到达的
至于如何确定最优情况一定能够到达，我们考虑将答案分段，每一段单独考虑，不同段不影响
简要题意：给定接下来 $n$ 天的股票价格 $a_i$，在第 $i$ 天，你可以选择买一支彩票或者卖一支彩票或者什么都不干，求 $n$ 天后你最多赚多少
$n\le 3\times 10^5$
简要题解：所以我们考虑维护一个当前可以被买入的所有东西的小根堆，每次判断卖出当前物品然后买入最便宜的东西是否赚，如果赚的话，我们就做这次生意
我们考虑如何实现反悔，我们将这次卖出的东西同样扔进小根堆里，如果之后将这个东西买入并卖出就相当于这个东西没有被买入过，即如果我们之前在 $i$ 买在 $j$ 卖，但是现在在 $i$ 买在 $k$ 卖更优，那么我们相当于获得了 $a_j-a_i+a_k-a_j=a_k-a_i$
需要注意到每次无论是否买入或卖出都需要将当前物品扔进小根堆
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在要求至多选择 $m$ 个数，需满足选择的任意两个数都不相邻，求最大价值
$n\le 5\times 10^5,|a_i|\le 10^6$
简要题解：我们考虑反悔自动机，我们令连续若干的只间隔 $1$ 的选择的数为一个选择区间 $[l,r]$($l$ 和 $r$ 一定选)，容易得到选择区间 $[l,r]$ 的长度一定是奇数，我们思考 $[l,r]$ 向外扩展所发生的变化，发现就是将 $[l,r]$ 内选择情况翻转，然后选择 $l-1$ 和 $r+1$，这个时候我们的选择区间从 $[l,r]$ 拓展到了 $[l-1,r+1]$，另外每扩展一次都相当于多选一个点，那么最终答案的结构一定是由若干个选择区间组成，且任意两个选择区间都想距至少 $2$，因为如果相距 $1$ 就是一个选择区间了
我们考虑用大根堆维护每个选择区间向外扩展的价值，每次贪心的选择扩展最大的区间，如果直到扩展完 $m$ 个点也没有两个必选区间相距小于 $2$，那么这肯定就是正确答案了
我们思考如果有两个必选区间相距为 $1$，那么这两个选择区间就相当于合并成了一个选择区间
这个时候我们会发现，区间扩展一定是从 $[l,r]$ 扩展到 $[l - 1, r+1]$ 吗，有没有可能是从 $[l,r]$ 扩展到 $[l - 1,r - 1]$ 呢，容易发现这是不可能发生的，如果 $[l - 1,r-1]$ 的价值大于 $[l,r]$，那么我们就不会到达 $[l,r]$，因为我们可能在 $[l+1,r-1]$ 时就会选择扩展点 $l - 1$ 然后合并成 $[l-1,r-1]$，因为在那个时候，价值最大的是扩展点 $l-1$ 而不是扩展 $[l+1,r-1]$
具体维护选择区间的方法大概就是选择区间 $[l,r]$ 内一个点表示这个选择区间，我们用一个左指针和一个右指针分别指向 $l-1$ 和 $r+1$，另外容易发现如果不管 $a$ 是一个序列还是一个环都不影响