cf1609F

写这个的目的是为了记录一下一种关于单调栈的新理解方式。

单调栈存在的目的就是为了维护后缀的min/max。

一个单调增的维护的是后缀min，反之是后缀max。

如果单调栈内的元素是 \(p_1,\cdots ,p_n\)，可以理解成\((p_1,p_2],(p_2,p_3),\cdots,(p_i,p_{i+1}],\cdots\) 段区间。

在维护min/max的过程中，单调栈自然带有着撤回的性质，考虑我们本质上是在维护上述区间，区间覆盖可以理解为减去原先的，加上后来的。

---

这道题让我深层认识到了单调栈，当我只想着“区间覆盖时”，et2006大佬的博客让我醍醐灌顶呀，真的只是在撤销。

link

这道题的思路很简单，如果真的理解了单调栈会很快做出来。

首先拆了popcount变为若干子问题。

分治感觉麻烦，直接考虑以 \(r\) 结尾时的答案。移动\(r\) 时候直接算贡献。

需要维护的只有 [min popcount = b] + [max popcount = b]。

复杂度竟然被单调栈均摊了，nbnb。