哪些元素可以删除 若 是一个长度至少为二的区间的最小值,那么该区间内至少有一个与 直接相邻的元素,且它比 大。反之,若有更大的相邻元素,选择这两个元素即可删除 。因此,一个元素可被删除,当且仅当其当前左邻或右邻中存在更大的元素。
保留位置的顺序 操作只删除元素,因此 必须是 的子序列。令 为值 的原始位置,检查
该检查也会拒绝 中出现重复值的情况。
待删除区间的条件 保留元素不会被删除,因此待删除元素分成若干间隙:第一个保留元素之前、相邻保留元素之间,以及最后一个保留元素之后。不同间隙的元素无法越过保留元素而相邻。
对于非空间隙,令 为其中最大值, 为相邻保留边界值中的较大者。首尾间隙仅有一个边界。能够删除整个间隙的充要条件是 。
必要性:删除 时必须有更大的相邻元素。间隙内部没有这样的值,因此只能来自保留边界,故必须有 。
充分性:按值从小到大删除间隙内的元素。只要还剩至少两个元素,最小者就在间隙中与一个更大的元素相邻,可以删除。最后只剩 时,它与满足 的边界相邻,也可删除。空区间自动满足条件。
实现 按顺序访问保留元素,每个前置间隙只扫描一次以求最大值。不存在的左边界以及空区间的最大值均设为 。真实值都是正数,因此同一比较式适用。最后单独检查末尾间隙。
仅当位置顺序与全部间隙条件成立时输出 YES,否则输出 NO。全局最大值 无法删除,因此 不含 时必定不可能。但包含最大值且为子序列仍不充分。例如 、 中, 的两侧保留边界为 ,无法删除。
时间和空间均为 。所有位置、数值及区间最大值均不超过 ,不需要大整数运算。
子任务 1 用位掩码表示保留位置,BFS 枚举全部合法区间操作。状态数至多为 ,逐步维护区间最小值可在 时间内枚举一个状态的操作。总时间为 ,空间为 ,足以处理 。子任务 2 使用上述线性判定。
Solution written by GPT6