解法思路

1. 核心观察

学生 $i$ 能通过考试的条件是：存在一个长度 ≥ 2 且包含 $i$ 的区间 $[l,r]$，满足：

这个条件确保区间内所有学生都能通过一次作弊达到要求。

2. 问题简化

我们只需要找到一组不相交的「好区间」（满足上述条件且长度 ≥ 2），使得这些区间覆盖的学生总数最大。

3. 动态规划解法

定义 $dp[i]$ 为前 $i$ 个学生中最多能通过的人数。

状态转移：

• 不选择第 $i$ 个学生通过：$dp[i] = dp[i-1]$
• 选择以 $i$ 结尾的区间 $[j,i]$ 通过：如果 $[j,i]$ 是好区间，则$$dp[i] = \max(dp[i], dp[j-1] + (i-j+1))$$

4. 寻找好区间

对于每个 $i$，我们需要找到所有满足条件的 $j < i$：

• 区间 $[j,i]$ 的长度 ≥ 2
• $\max(A_j \dots A_i) \ge \max(B_j \dots B_i)$

5. 优化方法

使用单调栈维护当前的最大值：

• 维护两个栈分别存储 $A$ 和 $B$ 的递减序列
• 当区间 $[j,i]$ 满足 $\max A \ge \max B$ 时，该区间就是好区间
• 对于每个 $i$，找到最小的 $j$ 使得 $[j,i]$ 是好区间，然后更新 DP 值

6. 算法流程

1. 初始化 DP 数组为 0
2. 维护两个单调栈用于快速查询区间最大值
3. 遍历每个学生 $i$：
   • 更新单调栈
   • 找到包含 $i$ 的好区间
   • 更新 DP 值
4. 最终答案为 $dp[N]$

复杂度分析

• 暴力 DP：$O(N^2)$，适用于 $N \le 5000$
• 优化后：$O(N)$，使用单调栈和双指针技巧

关键点总结

1. 理解作弊操作：区间内所有人获得区间最大值
2. 识别好区间：区间 $A$ 的最大值 ≥ 区间 $B$ 的最大值
3. 动态规划：选择最优的区间组合最大化通过人数
4. 单调栈优化：快速计算区间最大值

这种解法能够高效处理 $N \le 10^5$ 的大数据规模。