连续自闭一周后,短暂的快乐周末,然而上海在台风,不能出去快乐了。
(上一周欠的之后慢慢补吧
心路历程
因为小B的操作确定了,小A的操作可以直接贪,就还比较简单。
思路
二分小B操作了多少个回合。小B操作的越多,小A操作数非降,满足单调性。
验证就是小B操作了这么多回合之后,小A至少要花的回合数小于下一次小B操作的回合。
对于小A的操作,肯定是从最左或者最右开始操作,遇到要操作的地方就操作,这样很容易得到至少要花的回合数。
具体其实就是区间加,单点求值。可以线段树,可以树状数组,这样是\(O(n\log n\log m )\)的。
但是其实做到\(O( n \log n)\),就检查的时候可以线性:左端点加,右端点减,记录前缀增量,把他加到当前元素上,就可以做到区间加和单点求值。
最后再算一次至少要花的回合数。