P3370 [CTSC2017]密钥 题解

先来考虑最简单的暴力做法：从  开始，一个一个枚举  和  的数量，对其进行判断，最后求解。  

考虑优化一下：将  当作 ， 当作 。进行加和后再去比较。  

继续优化，可以使用前缀和。

根据题目中对“强的”的定义，我们可以证明如下结论：  

 强的字母（ 或 ）一共有  个。

 证明：我们将  看作 ， 看作 。  

 那么整个序列的前缀和就是由  分割成的若干段区间组成的。并且这些区间一定全为同号（即一个区间内，要么全为正，要么全为负）。

因此，前面两个小问就可以通过我们刚刚所推得的结论转化成第三个小问。  

特别地，我们将  看作 ，并令  为整个序列的前缀和。记原序列中  的位置为 。  

考虑一个强的 （其所在位置为 ）。  

若它在  后面，则满足   

否则，满足   

推广得到：若有  个强的 ，则一定存在  个  满足  或者 。

因此，对于每个  的位置，求出有序二元组  的第  小元素，就是最终的答案。

可以考虑计数排序（初赛刚搞过）。时间复杂度 。

Code: