Kevin5307的博客

博客

Universal Cup Season 3 Stage 7 Problem I 题解(锤子做法)

2024-08-25 23:00:57 By Kevin090228🍬

先进行一些分析。假设需要让 (a,b,c) 分别是冠亚季军,那么:

  1. a 会尽量多过题且不会罚时;
  2. c 只会过一个题,且是最后一次提交才通过;
  3. 除了这三个人之外的所有人都不过题。

更进一步的分析可以得到,b 可行的过题情况有两类:

  1. 在一次提交通过了唯一一个题,之前可能有罚时;
  2. 过了两个题,最后两发提交才通过。

预处理出每个人作为冠军和季军的罚时,称为 li,ri。只需要对于所有人作为亚军时的所有可行罚时情况,统计对应的 (冠军, 季军) 对的个数即可。

注意到,亚军过一个题且罚时大于 L 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 O(nL) 的,具体地,可以 O(c2)O(c+L) 来统计可行罚时情况。

然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况,此时需要减掉。

查询需要减掉的情况数,本质是进行 O(nL) 次如下询问:对于 [l,r],查询有多少 i 满足 [li,ri][l,r]。这是一个二维数点问题,可以离线下来做可持久化分块。更简单的做法是,容易发现,这 O(nL) 次询问中,只有 O(n) 次询问的区间 [l,r] 长度大于 20,所以可以提前预处理较短的区间的答案,对于较长的区间用主席树回答。

总时间复杂度是 O(nL+n×202+nlogn)。代码不是很难写,但是细节比较多。实现的时候不需要精细实现,复杂度多一点 log 或者 20 也没卡。

关于 std:我偷看了一眼,看上去就没有根号分治,应该是 polylog 的。大概可以,每个人作为亚军时,每个提交对应了罚时情况中的一个公差为 20 的等差数列,维护出区间之后大概处理一下,可以做到 O(nlogn) 或者 O(20×nlogn)

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。