题解：P12161 [蓝桥杯 2025 省 Java B] 研发资源分配

· · 题解

分3种情况：

1 ： 对于Pi，如果存在比他大的数，那么选择一堆大的里边，最小的就行了，ans+=i

2 ： 如果没有比他大的，查询是否有和他相等的，这个时候ans不加不减

3 : 如果前面两者情况都没有，那就在一堆小的里边，选择最小的，ans -= i

显而易见就是区间查 + 单点修改 ,从最大的开始，从后往前， 用线段树暴力就行了，时间复杂度就是O（n*2logn）