题解

思路

处理完若干城市后，令 $f_k$ 表示能够选出长度为 $k$ 的合法子序列时，最后一个访问日期的最小可能值。规定 $f_0=0$。所有有限的 $f_k$ 严格递增。

加入新区间 $[l,r]$ 时，若已有状态满足 $f_k<r$，就可以在新区间中选择

并把长度扩展到 $k+1$。从大到小枚举 $k$ 即可得到朴素动态规划。

做法

设 $a$ 为第一个满足 $f_a\ge l$ 的位置，$b$ 为第一个满足 $f_b\ge r$ 的位置；若不存在，则位置取在当前序列末尾之后。一次转移把状态序列改为：

• 新的 $f_a=l$；
• 对 $a<j\le b$，新的 $f_j$ 等于旧的 $f_{j-1}+1$；
• 其他位置不变。

令 $g_k=f_k-k$。上述转移就变成：在序列 $g$ 的第 $a$ 个位置插入 $l-a$，并在原来的第 $b$ 个位置存在时将其删除。被右移的中间段无需修改，因为下标和值同时增加一。

用隐式 Treap 按下标维护 $g$。由于 $f_k=g_k+k$ 单调，查询第一个不小于给定值的位置时，可以根据左子树大小计算当前节点对应的 $f_k$，再沿树向左或向右查找。插入、删除和两次边界查询都只需对平衡树进行常数次分裂与合并。

子任务 1 可以枚举城市子集。固定一个子序列后，从前往后总选择不小于前一日期加一的最早开放日；若超过右端点则该子序列不可行。

子任务 2 直接维护数组 $f$，对每个区间从大到小枚举全部已有长度。

正确性证明

对任意长度 $k$，只保留最后日期最小的方案不会损失最优解，因为更小的最后日期至少能够接上原方案之后可接的所有区间。因此 $f_k$ 的状态定义充分。

处理区间 $[l,r]$ 时，扩展状态 $k$ 的最小可选日期必为 $\max(l,f_k+1)$，且它可行当且仅当 $f_k<r$。这正是朴素转移枚举的全部可能，故更新后的 $f$ 仍准确描述每个长度的最小末尾日期。

根据 $a,b$ 的定义，$k<a$ 时扩展值为 $l$，其中只有最大的 $k=a-1$ 可能改善状态；$a\le k<b$ 时扩展值为 $f_k+1$；$k\ge b$ 时不可扩展。因此插入并删除的序列变换与朴素转移完全等价。隐式 Treap 仅加速这一等价变换，不改变状态值。

最终，有限状态的最大下标就是可行子序列的最大长度，所以算法输出正确答案。

复杂度

子任务 1 的时间复杂度为 $O(n2^n)$，空间复杂度为 $O(n)$。

子任务 2 的时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

完整算法每个区间进行常数次平衡树操作，期望时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。