题解：AT_abc436_f [ABC436F] Starry Landscape Photo

· · 题解

题意

给定排列 P，求不同的区间前 b 小的集合个数，b 未给定。

Solution

我们枚举最大值，这样所有的区间都可以由当前数扩展出去。

然后我们注意到一件事情，由于我们枚举的是最大值 mx，所以往外扩展时若当前数 <mx 就一定会被加入集合，反之一定不会。

我们记左侧小于等于 P_i 的数的个数为 pre_i（包含 P_i），右侧为 suf_i，则两边组合起来的方案数就是 pre_i\times suf_i。

简单用树状数组维护一下即可做到 O(n\log{n})。

AC Code