先进行一些分析。假设需要让 (a,b,c) 分别是冠亚季军,那么:
- a 会尽量多过题且不会罚时;
- c 只会过一个题,且是最后一次提交才通过;
- 除了这三个人之外的所有人都不过题。
更进一步的分析可以得到,b 可行的过题情况有两类:
- 在一次提交通过了唯一一个题,之前可能有罚时;
- 过了两个题,最后两发提交才通过。
预处理出每个人作为冠军和季军的罚时,称为 li,ri。只需要对于所有人作为亚军时的所有可行罚时情况,统计对应的 (冠军, 季军) 对的个数即可。
注意到,亚军过一个题且罚时大于 L 的所有可行罚时中只需要保留最小的那个即可。所以可以根号分治统计所有人作为亚军的可行罚时情况。时间复杂度是 O(n√L) 的,具体地,可以 O(c2) 或 O(c+L) 来统计可行罚时情况。
然后计算出合法的数量。可能存在统计的时候多算冠军和季军是同一个人的情况,此时需要减掉。
查询需要减掉的情况数,本质是进行 O(n√L) 次如下询问:对于 [l,r],查询有多少 i 满足 [li,ri]⊆[l,r]。这是一个二维数点问题,可以离线下来做可持久化分块。更简单的做法是,容易发现,这 O(n√L) 次询问中,只有 O(n) 次询问的区间 [l,r] 长度大于 20,所以可以提前预处理较短的区间的答案,对于较长的区间用主席树回答。
总时间复杂度是 O(n√L+n×202+nlogn)。代码不是很难写,但是细节比较多。实现的时候不需要精细实现,复杂度多一点 log 或者 20 也没卡。
关于 std:我偷看了一眼,看上去就没有根号分治,应该是 polylog 的。大概可以,每个人作为亚军时,每个提交对应了罚时情况中的一个公差为 20 的等差数列,维护出区间之后大概处理一下,可以做到 O(nlogn) 或者 O(20×nlogn)。