[题目总结 #1] 静态序列区间查询问题（未完）

[题目总结 #1] 静态序列区间查询问题

前言

不久前遇到一批这种题，我发现自己思路很单一，只想着莫队、分块、线段树，但是其实可能有其他巧妙的做法，而且就算是用分块、线段树维护的东西也有我没想到的。总体来说，在这种题上，自己的思维太固化、自己太依赖思维惯性，又不熟悉各种套路。于是总结。

2024.11.7 日晚约 19:50，做题已倦，于是开写。

题目

给一个长度为 \(n\) 的序列和 \(q\) 个询问，每次查询一段区间的某种信息。

事实上不一定是一段区间，也可以是给出两个点（后面提到的“两点问题”）。

说明

本文中涉及的一些思路不止是静态时可以使用。

解法

一、简单线段树（查询时合并结点信息） & 简单分块（查询时合并结点信息）

可能是最常见的做法。

不要忽视简单线段树的作用。线段树是基础的合并式的数据结构，遇到这种题应当首先思考信息能否合并，然后才是莫队那种一位位移动的做法。

• 思考每个结点（块）维护哪些信息，如何合并结点（块）信息（PushUp、查询时）。
• 线段树：合并：PushUp 时、查询时。
• 分块：相比线段树的优势是不需要 PushUp（但对于一些问题来说仍需要在查询时合并块信息）。这种题分块优势不大，这一部分下面的内容都是线段树。

如何思考维护哪些信息？

• 以区间最大子段和为例：要维护结点区间内最大子段和，考虑如何通过合并结点得到它，那么就需要维护结点区间的最大前缀和和最大后缀和；考虑如何合并结点得到这两者，就需要维护区间和。
• 方法总结：考虑直接维护要求的信息，考虑怎么合并，通过维护其他信息来实现。思考递归下去，直到不需要再维护其他信息。

合并结点时的思考方式是什么？

• 考虑左边的右端点和右边的左端点拼在一起会发生什么。
• 考虑左边的后缀和右边的前缀拼在一起会发生什么。

有对于某种问题维护某种信息的套路吗？

• 有。

• 最优子段（即子区间）问题：

  • 区间最大子段和：如上文。
  • \(01\) 序列，问区间最长 \(01\) 交错（不含连续的 \(0\) 或连续的 \(1\)）子段的长度：和区间最大子段和类似，每个结点维护答案、前缀、后缀即可。不同的是不用维护整个结点区间全选的信息（如：区间最大子段和做法中的区间和），因为区间最大子段和可以通过之后的东西把之前负数的影响抹去，但是这个问题不只要有连续的 \(0/1\) 就不行了，所以新的前缀信息只需要用左边的前缀信息和右边的前缀信息来合并，新的后缀信息同理。具体见代码。（P6492 [COCI2010-2011#6] STEP）
  • 总结：结点区间的答案信息；左结点的右端点、后缀；右结点的左端点、前缀；结点区间全选的信息。

• 合法子段计数问题：我还没怎么想，不知道能不能用简单线段树做。

• 两点问题：

  • \(2 \times n\) 格子图，查两点间最短路（边相邻格子有边，但有格子不能走）：（引用题解）”用线段树的每个结点维护第 \(l\) ~ \(r\) 列这段 \(2 \times (r - l + 1)\) 的方格左上到右上、左上到右下，左下到右上、左下到右下的最短路的值。对两个结点答案的合并，对于经过 \((1, mid)\) 和 \((2, mid)\) 对应答案取 \(\min\) 就行。“（2024.8.21 考试 family 一题）
  • 总结：维护的区间端点之间的关系信息。为什么不用维护区间内每一对结点的关系？因为 线段树可以保证恰好合并出你想要的那个区间，而此时区间的端点就是查询的那两个点。

二、查询时不合并的线段树 & 不合并的分块

• 线段树：
  • 相比分块的优势 \(1\)：模板化，好写。完整（可以直接 完整 地得到想要的区间）。
  • 相比分块的优势 \(2\)：一些时候时间复杂度较小。
• 分块：
  • 结构上的两个特点：
    • 扁平。
    • 平衡。
  • 相比线段树的优势 \(1\)（扁平）：不需要 PushUp，可以用块内的东西较暴力地求出块信息。
  • 相比线段树的优势 \(2\)（平衡）：可以方便灵活地平衡复杂度。
  • 上述两点给了暴力更多的发挥余地，可以很灵活地维护信息。
  • 区间查询仍需要考虑块间的处理，于是在查询时特殊处理（如：跳；……）。（都用分块了就别老惦记着合并了。）

例题？

• P5397 [Ynoi2018] 天降之物：虽然不是静态的，我忘了做法了 /ll。
• 2024.10.19 考的联考题的 T3：题意清楚，但不好概括。大概是要从一个点往左跳。
  • 分块思路：用分块加速跳的过程，似乎类似“弹飞绵羊”那题。这是我考场上写的做法，但是细节太多，我写不来。
  • 线段树思路：每个结点维护从它的区间右边一段里某个位置往左跳，在这个区间里会跳到的最左边的位置。题目保证了要维护的那“一段”很短。查询时不需要合并，只需要跳就行了（虽然可能查询时合并也行，但合并的话好像查询的复杂度更高，总复杂度好像变化不大）。
    • 本质是线段树维护映射。其实是线段树维护了很多信息，而每次询问只需要用一些，所以不需要全部合并。
• 弹飞绵羊（分块做法）。（？）

这种做法的本质？

• 由上面的例题思路可知，其实是要预处理很多信息，但是每次查询时只会用到一部分信息，而且合并的复杂度较高。于是使用非合并的方法查询。

2024.11.7