连续段计数问题小记()

给定一个长度为 \(n\) 的一个排列,如果区间 \([l,r]\) 之间的数是连续的,那么我们称这个区间时一个连续段。

比如 \([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]\)。

这些连续段有一个共同的特点:区间长度等于值域大小,即 \(\max-\min+1=r-l+1\)。

移项可得:\(\max-\min-r+l=0\),判断是否为连续段就采用的是这种方法。

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

由于上面我们需要通过维护 \(\max,\min\) 维护每个左端点。前面的 \(\max,\min\) 可以用单调栈维护,整体用线段树记录。

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

CF526F Pudding Monsters

给定长度为 \(n(n\le 3\times 10^5)\) 的排列,求其中连续段数量。

给定长度为 \(n(n\le 3\times 10^5)\) 的排列,求其中连续段数量。

枚举右端点,用单调栈更新左端点,每次询问 \(0\) 的个数。

CF997E Good Subsegments

给定长度为 \(n(n\le 1.2\times 10^5)\) 的排列,有 \(q(q\le 1.2\times 10^5)\) 次询问,每次询问一段区间 \([l,r]\) 内的连续段数量。

给定长度为 \(n(n\le 1.2\times 10^5)\) 的排列,有 \(q(q\le 1.2\times 10^5)\) 次询问,每次询问一段区间 \([l,r]\) 内的连续段数量。

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

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

如果直接维护 \(0\) 的个数会比较麻烦,但是题目中有一个重要的性质保证给定的是排列。这表示 \(\max-\min-r+l\) 一定 \(\ge 0\),只有区间最小值会被减为 \(0\)。那么记下最小值和次数即可。

具体维护以下信息:

  • 当前区间最小值 \(valnowmin\);
  • 当前区间最小值个数 \(cntnowmin\);
  • 当前增加值 \(vallaz\);
  • 这个区间有多少次最小值到达了 \(0\) 但子节点里没有计入答案 \(pushed\);
  • 答案数量 \(ans\)。

每移动一次右端点记录给整棵树加一次 \(pushed\) 即可。

P4747 [CERC2017]Intrinsic Interval

咕咕咕ing

P6795 [SNOI2020] 排列

咕咕咕ed

————————

给定一个长度为 \(n\) 的一个排列,如果区间 \([l,r]\) 之间的数是连续的,那么我们称这个区间时一个连续段。

比如 \([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]\)。

这些连续段有一个共同的特点:区间长度等于值域大小,即 \(\max-\min+1=r-l+1\)。

移项可得:\(\max-\min-r+l=0\),判断是否为连续段就采用的是这种方法。

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

由于上面我们需要通过维护 \(\max,\min\) 维护每个左端点。前面的 \(\max,\min\) 可以用单调栈维护,整体用线段树记录。

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

CF526F Pudding Monsters

给定长度为 \(n(n\le 3\times 10^5)\) 的排列,求其中连续段数量。

给定长度为 \(n(n\le 3\times 10^5)\) 的排列,求其中连续段数量。

枚举右端点,用单调栈更新左端点,每次询问 \(0\) 的个数。

CF997E Good Subsegments

给定长度为 \(n(n\le 1.2\times 10^5)\) 的排列,有 \(q(q\le 1.2\times 10^5)\) 次询问,每次询问一段区间 \([l,r]\) 内的连续段数量。

给定长度为 \(n(n\le 1.2\times 10^5)\) 的排列,有 \(q(q\le 1.2\times 10^5)\) 次询问,每次询问一段区间 \([l,r]\) 内的连续段数量。

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

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

如果直接维护 \(0\) 的个数会比较麻烦,但是题目中有一个重要的性质保证给定的是排列。这表示 \(\max-\min-r+l\) 一定 \(\ge 0\),只有区间最小值会被减为 \(0\)。那么记下最小值和次数即可。

具体维护以下信息:

  • 当前区间最小值 \(valnowmin\);
  • 当前区间最小值个数 \(cntnowmin\);
  • 当前增加值 \(vallaz\);
  • 这个区间有多少次最小值到达了 \(0\) 但子节点里没有计入答案 \(pushed\);
  • 答案数量 \(ans\)。

每移动一次右端点记录给整棵树加一次 \(pushed\) 即可。

P4747 [CERC2017]Intrinsic Interval

咕咕咕ing

P6795 [SNOI2020] 排列

咕咕咕ed