操作 1 无需优化,来看操作 2。
对于操作 2,很容易想到一种基于暴力的优化:
1、对序列 a 排序。 2、二分查找第一个大于 0 的数的下标,计为 p。 3、累加序列 a 中从下标为 p 的数字到最后一个(预处理前缀和)。 这样优化的时间复杂度最坏为 O(mlogn),空间复杂度为 O(n)。
注意:
1、开 long long。 2、p 要初始化成 n+1(如果没有比 0 大的数就会输出 0)。 3、本题中所用的前缀和是倒序的。
By signing up a 星高度 universal account, you can submit code and join discussions in all online judging services provided by us.
Using your 星高度 universal account