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

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

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

BCD 在难度顺序不存在逆序时无法进行吗?

返回题目

题解

令 PjP_jPj​ 为第 jjj 道题目之前的最大难度,QjQ_jQj​ 为其之后的最小难度。如果前面没有题目,则令 Pj=0P_j=0Pj​=0;如果后面没有题目,则令 Qj=M+1Q_j=M+1Qj​=M+1。第一道无法解出的题目为第 jjj 道题目的受害者人数为

max⁡(0,Aj−max⁡(Pj,Qj))\max\bigl(0,A_j-\max(P_j,Q_j)\bigr)max(0,Aj​−max(Pj​,Q

。

对所有 jjj 将上述值求和。先从右向左扫描求出 QjQ_jQj​,再从左向右扫描,在维护 PjP_jPj​ 的同时累加答案。时间复杂度和空间复杂度均为 O(N)。

证明

当题目按照难度排序时,实力为 sss 的参赛者会解出所有难度不超过 sss 的题目。因此,成为受害者的充要条件是:在第一道使其停止的题目之后,仍存在该参赛者能够解出的题目。

第 jjj 道题目是第一道无法解出的题目的充要条件是 Pj≤s<AjP_j\leq s<A_jPj​≤,而后面存在可以解出的题目的充要条件是 。同时满足这两个条件的实力取值数量为 。每名受害者都有唯一的第一道无法解出的题目,因此求和时既不会重复,也不会遗漏。

j​
)
)
O(N)
O(N)
s<
Aj​
Qj≤sQ_j\leq sQj​≤s
max⁡(0,Aj−max⁡(Pj,Qj))\max(0,A_j-\max(P_j,Q_j))max(0,Aj​−max(Pj​,Qj​))