主要思路

这个题转换一下就是：给你一个排列，然后算有多少个区间使得区间内的数可以构成一个连续的数列。

主要思路

一开始想了一个假的，后面写完了之后才意识到哪里错了，就很傻逼。

首先贪心的知道，肯定是第 \(i\) 小的数位于 \(K + i – 1\) 的位置上。我们算答案的时候会发现无非就是把贡献根据绝对值的拆法进行分开处理，一部分是 \((a_i – rk_i) – (k – 1)\)，还有一部分是 \((k – 1) – (a_i – rk_i)\)。所以我们需要一个数据结构来拆分这两个部分。

首先我们知道这两个部分肯定是连续的两段，因为前后的 Delta 都至多为 \(1\)。知道这个性质之后，我们其实可以尝试用主席树来搞区间内的段。考虑用势能线段树的那一套，我们可以把段一直下传，直到段完整为止。

对于完整的段，发现其实就是给上面那个贡献式子套 \(\sum\)，而且发现套 \(\sum\) 的时候要记录这一段和的左端点，这样就可以用等差数列直接搞了。

主要思路

第一次做到线段树维护单调栈的题，来写一写博客。

首先这个题求的就是 \(ans = \min_{i \in [n, 2n)} \max_{j \in [i – n + 1, i]} a_j + i – j\)，换一下就是 \(ans = (\min_{i \in [1, n)} \max_{j \in [i, i + n – 1]} a_j + i – j) + n – 1\)。

我们可以考虑做 \(B_i = a_i – i\)，然后再去做 \(\min\) 值。然而这样复杂度还是很高。我们考虑静态的问题时，发现其实这题可以做到 \(\Theta(n)\)，因为这个其实用一个反着的（从右到左）单调栈就行了。

放到动态问题上，可以尝试用线段树去搞搞：合并的时候，先保留右子树的内容，然后尝试在左子树里进行二分，找到队尾即可。