题目大意

有 $N$ 个按时间排序的庆典，需要将每个庆典分配给两个王朝之一（1 或 2）。每个学者提出约束：

• 王朝1（马奶酒）相邻庆典间隔在 $[KL_i, KR_i]$
• 王朝2（蜂蜜）相邻庆典间隔在 $[ML_i, MR_i]$

目标是找到满足至少一个学者约束的方案，使得可疑度指标（同一王朝内连续统治次数）最小。

解题思路

核心思想

动态规划 + 数据结构优化

1. DP状态设计：维护两个王朝的转移代价
2. 单调队列优化：快速找到满足时间间隔约束的最优前驱
3. 全局标记技巧：高效处理代价更新

算法流程详解

1. 状态定义

• T[0].f[i]：前 i 个庆典，第 i 个属于王朝1的最小可疑度
• T[1].f[i]：前 i 个庆典，第 i 个属于王朝2的最小可疑度

2. 转移策略

对于每个位置 i：

• 王朝1：可以从满足时间间隔约束的王朝2位置转移过来
• 王朝2：可以从满足时间间隔约束的王朝1位置转移过来

3. 单调队列优化

• Q[0]：维护可以转移到王朝2的王朝1位置
• Q[1]：维护可以转移到王朝1的王朝2位置
• 利用时间单调性，快速找到最优前驱

4. 全局标记技巧

• 使用 tag 记录全局增加的代价
• 避免逐个更新，提高效率

复杂度分析

• 时间复杂度：$O(N \times S)$

  • 对每个学者进行 $O(N)$ 的DP
  • 单调队列操作均摊 $O(1)$

• 空间复杂度：$O(N)$

总结

本题的亮点在于：

1. 巧妙的DP状态设计：同时维护两个王朝的代价，通过交替转移最小化可疑度

2. 单调队列优化：利用时间序列的单调性，快速找到满足间隔约束的最优前驱

3. 全局标记技巧：通过标记传递避免重复计算，提升效率

4. 双指针维护：配合单调队列，确保队列中所有位置都满足时间间隔约束