连续段计数问题小记

给定一个长度为 n" role="presentation" style="position: relative;">n$n$ 的一个排列，如果区间 [l,r]" role="presentation" style="position: relative;">[l,r]$[l,r]$ 之间的数是连续的，那么我们称这个区间时一个连续段。

比如 [1,3,2,5,4]" role="presentation" style="position: relative;">[1,3,2,5,4]$[1,3,2,5,4]$ 中的连续段有：[1,1],[1,3],[1,5],[2,2],[2,3],[2,5],[3,3],[4,4],[4,5],[5,5]" role="presentation" style="position: relative;">[1,1],[1,3],[1,5],[2,2],[2,3],[2,5],[3,3],[4,4],[4,5],[5,5]$[1,1],[1,3],[1,5],[2,2],[2,3],[2,5],[3,3],[4,4],[4,5],[5,5]$。

这些连续段有一个共同的特点：区间长度等于值域大小，即 max−min+1=r−l+1" role="presentation" style="position: relative;">max−min+1=r−l+1$max-min+1=r-l+1$。

移项可得：max−min−r+l=0" role="presentation" style="position: relative;">max−min−r+l=0$max-min-r+l=0$，判断是否为连续段就采用的是这种方法。

有一些题目会询问关于连续段的问题，很多都是数区间个数。数区间个数的问题一般可以分治或固定端点，下边就采用了固定端点的方法，枚举右端点，处理所有左端点的询问。

由于上面我们需要通过维护 max,min" role="presentation" style="position: relative;">max,min$max,min$ 维护每个左端点。前面的 max,min" role="presentation" style="position: relative;">max,min$max,min$ 可以用单调栈维护，整体用线段树记录。

那么我们就来看一些具体问题吧！

CF526F Pudding Monsters

给定长度为 n(n≤3×105)" role="presentation" style="position: relative;">n(n≤3×105)$n(n\le 3\times {10}^5)$ 的排列，求其中连续段数量。

枚举右端点，用单调栈更新左端点，每次询问 0" role="presentation" style="position: relative;">0$0$ 的个数。

CF997E Good Subsegments

给定长度为 n(n≤1.2×105)" role="presentation" style="position: relative;">n(n≤1.2×105)$n(n\le 1.2\times {10}^5)$ 的排列，有 q(q≤1.2×105)" role="presentation" style="position: relative;">q(q≤1.2×105)$q(q\le 1.2\times {10}^5)$ 次询问，每次询问一段区间 [l,r]" role="presentation" style="position: relative;">[l,r]$[l,r]$ 内的连续段数量。

好像是上一题的严格加强版捏。

其他和上面一模一样，我们还需要维护历史答案，那就改改线段树吧！

如果直接维护 0" role="presentation" style="position: relative;">0$0$ 的个数会比较麻烦，但是题目中有一个重要的性质保证给定的是排列。这表示 max−min−r+l" role="presentation" style="position: relative;">max−min−r+l$max-min-r+l$ 一定 ≥0" role="presentation" style="position: relative;">≥0$\ge 0$，只有区间最小值会被减为 0" role="presentation" style="position: relative;">0$0$。那么记下最小值和次数即可。

具体维护以下信息：

• 当前区间最小值 valnowmin" role="presentation" style="position: relative;">valnowmin$valnowmin$；
• 当前区间最小值个数 cntnowmin" role="presentation" style="position: relative;">cntnowmin$cntnowmin$；
• 当前增加值 vallaz" role="presentation" style="position: relative;">vallaz$vallaz$；
• 这个区间有多少次最小值到达了 0" role="presentation" style="position: relative;">0$0$ 但子节点里没有计入答案 pushed" role="presentation" style="position: relative;">pushed$pushed$；
• 答案数量 ans" role="presentation" style="position: relative;">ans$ans$。

每移动一次右端点记录给整棵树加一次 pushed" role="presentation" style="position: relative;">pushed$pushed$ 即可。

P4747 [CERC2017]Intrinsic Interval

咕咕咕ing

P6795 [SNOI2020] 排列

咕咕咕ed