题解

思路

分段动态规划

不参加作弊的人可以看成一个长度为 $1$ 的区间，因此任意合法方案都等价于把整个序列划分成若干连续段。

记

$$W(x,y)=\sum_{p=x}^{y}[l_p\le \max_{x\le q\le y}a_q\le r_p]$$

为把 $[x,y]$ 作为一段时满足要求的人数。令 $f_i$ 表示前 $i$ 人的最优答案，则

$$f_i=\max_{1\le x\le i}\{f_{x-1}+W(x,i)\},\qquad f_0=0.$$

直接计算每个 $W$ 可得到子任务 1 的 $O(n^3)$ 算法。

单调分数子任务

当 $a$ 不降时，区间 $[x,i]$ 的最大值恒为 $a_i$。固定一个人 $j$，当右端点 $i\ge j$ 扫描时，条件 $l_j\le a_i\le r_j$ 只会经历“尚未进入、满足、已经离开”三种连续阶段。

当它进入满足阶段时，对所有 $x\le j$ 的候选值加 $1$；离开时再减 $1$。线段树维护所有已出现左端点的最大候选值，并在处理右端点 $i$ 前把新候选 $x=i$ 置为 $f_{i-1}$，即可在 $O(n\log n)$ 时间完成子任务 2。

做法

一般情形的贡献事件

现在固定某个人 $j$，研究他会给哪些状态 $(x,i)$ 贡献 $1$，其中 $x\le j\le i$。

定义四个边界：

• $R_L=1+\max\{p\le j\mid a_p>r_j\}$，集合为空时最大值取 $0$；
• $L_L=\max\{p\le j\mid a_p\ge l_j\}$，集合为空时取 $0$；
• $L_R=\min\{p\ge j\mid a_p\ge l_j\}$，集合为空时取 $n+1$；
• $R_R=\min\{p\ge j\mid a_p>r_j\}$，集合为空时取 $n+1$。

若 $a_j>r_j$，任何包含 $j$ 的段都不可能让他满足要求，可以直接跳过。否则：

1. 在右端点刚到 $j$ 时，恰有 $x\in[R_L,L_L]$ 使左半段最大值落在 $[l_j,r_j]$，因此在时刻 $j$ 对该区间加 $1$；
2. 到时刻 $L_R$，右半段第一次提供不小于 $l_j$ 的值，于是此前尚未满足的 $x\in[L_L+1,j]$ 也全部贡献 $1$；
3. 到时刻 $R_R$，右半段第一次出现大于 $r_j$ 的值，所有 $x\in[R_L,j]$ 的贡献同时消失，因此对该区间减 $1$。

若 $L_R=R_R$，第二、三个事件发生在同一时刻，新增贡献会立刻抵消，正好表示最大值从“小于下界”直接跳到“大于上界”。因此这些事件也覆盖所有相等和越界边界。

每个人至多产生三次区间加法。用一棵静态最大值线段树分别求“左侧最后一个”和“右侧第一个”达到给定阈值的位置，再用另一棵懒标记线段树维护

$$V_i(x)=f_{x-1}+W(x,i),$$

总复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

正确性证明

引理 1

任意合法方案都与某个完整连续分段一一对应，且每一段的得分贡献为 $W$。

证明。 每个作弊区间本来就互不相交。把未被覆盖的位置各自补成单点段，不改变其分数；反之，每个长度大于 $1$ 的段可作为一次作弊，单点段可选择不作弊。因此两种描述等价。∎

引理 2

固定 $j$。在右端点 $i<R_R$ 时，没有 $a_p>r_j$ 出现在 $[j,i]$；此时 $j$ 是否贡献，只取决于左右两侧最大值是否至少为 $l_j$。在 $i\ge R_R$ 时，$j$ 永不贡献。

证明。 区间最大值是 $\max(\max_{x\le p\le j}a_p,\max_{j\le p\le i}a_p)$。一旦任一侧出现大于 $r_j$ 的值，上界永久失败；在此之前，上界成立，下界成立当且仅当至少一侧最大值达到 $l_j$。∎

引理 3

上述三类事件在每个时刻、对每个候选左端点，恰好维护了人 $j$ 对 $W(x,i)$ 的贡献。

证明。 当 $i=j$ 时，左侧最大值位于允许区间的左端点集合恰为 $[R_L,L_L]$。到 $L_R$ 后右侧达到下界，使余下仍未越过左侧上界的左端点 $[L_L+1,j]$ 全部满足。到 $R_R$ 后右侧越过上界，整个 $[R_L,j]$ 全部失效。三个区间不重不漏，并由引理 2 覆盖所有时刻。∎

定理

算法输出全局最优答案。

证明。 由引理 3，处理完时刻 $i$ 的全部事件后，线段树叶子 $x$ 的值恰为 $f_{x-1}+W(x,i)$。取全局最大值即得到动态规划转移式中的 $f_i$。结合引理 1，归纳可知 $f_n$ 等于所有合法方案的最大满足人数。∎

复杂度

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。