DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

删除最小值

返回题目

题解

哪些元素可以删除 若 xxx 是一个长度至少为二的区间的最小值,那么该区间内至少有一个与 xxx 直接相邻的元素,且它比 xxx 大。反之,若有更大的相邻元素,选择这两个元素即可删除 xxx。因此,一个元素可被删除,当且仅当其当前左邻或右邻中存在更大的元素。

保留位置的顺序 操作只删除元素,因此 AAA 必须是 PPP 的子序列。令 pos[v]\mathrm{pos}[v]pos[v] 为值 vvv 的原始位置,检查

pos[A1]<pos[A2]<⋯<pos[AM].\mathrm{pos}[A_1]<\mathrm{pos}[A_2]<\cdots<\mathrm{pos}[A_M].pos[A1​]<pos[A2​

该检查也会拒绝 AAA 中出现重复值的情况。

待删除区间的条件 保留元素不会被删除,因此待删除元素分成若干间隙:第一个保留元素之前、相邻保留元素之间,以及最后一个保留元素之后。不同间隙的元素无法越过保留元素而相邻。

对于非空间隙,令 ggg 为其中最大值,bbb 为相邻保留边界值中的较大者。首尾间隙仅有一个边界。能够删除整个间隙的充要条件是 g<bg<bg<b。

必要性:删除 ggg 时必须有更大的相邻元素。间隙内部没有这样的值,因此只能来自保留边界,故必须有 b>gb>gb>g。

充分性:按值从小到大删除间隙内的元素。只要还剩至少两个元素,最小者就在间隙中与一个更大的元素相邻,可以删除。最后只剩 ggg 时,它与满足 b>gb>gb>g 的边界相邻,也可删除。空区间自动满足条件。

实现 按顺序访问保留元素,每个前置间隙只扫描一次以求最大值。不存在的左边界以及空区间的最大值均设为 000。真实值都是正数,因此同一比较式适用。最后单独检查末尾间隙。

仅当位置顺序与全部间隙条件成立时输出 YES,否则输出 NO。全局最大值 NNN 无法删除,因此 AAA 不含 NNN 时必定不可能。但包含最大值且为子序列仍不充分。例如 P=[6,1,5,2,3,4]P=[6,1,5,2,3,4]P=[6,1,5,2,、 中, 的两侧保留边界为 ,无法删除。

时间和空间均为 O(N+M)O(N+M)O(N+M)。所有位置、数值及区间最大值均不超过 200 000200\,000200000,不需要大整数运算。

子任务 1 用位掩码表示保留位置,BFS 枚举全部合法区间操作。状态数至多为 2N2^N2N,逐步维护区间最小值可在 O(N2)O(N^2)O(N2) 时间内枚举一个状态的操作。总时间为 O(2NN2)O(2^N N^2)O(2,空间为 ,足以处理 。子任务 2 使用上述线性判定。

Solution written by GPT6

]
<
⋯<
pos[AM​].
3
,
4
]
A=[6,1,2,3,4]A=[6,1,2,3,4]A=[6,1,2,3,4]
555
1,21,21,2
N
N2
)
O(2N+N)O(2^N+N)O(2N+N)
N≤10N\leq10N≤10