Luogu5069 [Ynoi2015] 纵使日薄西山

题意：对于序列 ，不断进行如下操作 ：

选择 中最靠左的最大值 ，将 都减去一，然后将小于 的元素置为 。

记 为：整个序列变为 之前进行的操作数。

维护一个长为 的序列 ，支持单点修改，查询 的值。

，时限 。

---

先不考虑修改，思考如何求出 。

观察：若我们操作了 ，之后总有 ，故不会再以 为中心进行操作。

其他可能的操作均不再会影响 的值，故 必须要使用 次操作。

不妨将过程等价地改为：每次选出最靠左的最大值 ，将 变为 ，次数加上 。

于是答案就是所有被操作的位置的和。

进一步观察，对于单调不增的序列，被操作的下标是所有奇数。

对于一般的序列，我们将其看成若干段单调序列。

对于“山峰”，必然有贡献。

对于“山坡”上的点，下标奇偶性与对应“山峰”相同的位置有贡献。

对于“山谷”，必须奇偶性与相邻的两个山峰都相同才有贡献。

用树状数组分别维护奇下标与偶下标的部分和。用 std::set 维护山峰和山谷。

复杂度 。

本题对时间常数的要求较为宽松，可以适当简化代码。