前言

题目

给一个有一个长度为 $n$ 的数组 $a$ 。

数组 $a$ 的前缀和定义为 $s_{i} = \sum_{j = 1}^{i} a_{j}$ (对于所有的 $1 \leq i \leq n$ )，规定 $s_{0} = 0$ 。

数组 $a$ 的前缀和的前缀最大值为 $m a x_{i} = {max}_{j = 0}^{i} s_{j}$ (对于所有的 $1 \leq i \leq n$ )。

数组 $a$ 的 $1$ 类和谐度为 $m a x_{i}$ 中不同的元素数量。

数组 $a$ 的 $2$ 类和谐度为所有 $a$ 的所有排列中 $1$ 类和谐度的种类数。

现在有一个长度为 $n$ 的数组 $b$ 。

给出 $q$ 个询问，每个询问包含两个整数 $l, r$ ，求 $b_{l}, b_{l + 1}, b_{l + 2}, \dots, b_{r}$ 的 $2$ 类和谐度为多少。

需要一个很重要的技巧：求某种属性的种类数可以用上限减去下限。

有个细节的突破点 $s_{0} = 0$ ，这里就给我们提示了， $1$ 类和谐度中的 $m a x_{i} \geq 0$ ，那么这里的上限就是把区间内的正数放在前面，负数放在后面；下限反过来即可。

我们还需要证明上下限之间的种类数都可以构造出来：

很简单，我们只需要把前面的 $k$ 正数放在负数后面，种类数就会减 $k$ ，这是显而易见的。

线段树合并的板子题。

定义每个节点 $r t$ 表示的区间 $[l, r]$ 上有 $s u m, m a x x, l m a x, r m a x$ 分别表示区间 $[l, r]$ 中所有值的和，最大子段和，以 $l$ 为左端点的最大子段和和以 $r$ 为右端点的最大子段和。

那么易得（画个图就很好理解了）：

$r t_{s u m} = l s o n_{s u m} + r s o n_{s u m}$ ；

$r t_{l m a x} = max (l s o n_{l m a x}, l s o n_{s u m} + r s o n_{l m a x})$ ；

$r t_{r m a x} = max (r s o n_{r m a x}, r s o n_{s u m} + l s o n_{r m a x})$ ；

$r t_{m a x x} = max (l s o n_{m a x x}, r s o n_{m a x x}, l s o n_{r m a x} + r s o n_{l m a x})$ 。