menu zcmimi's blog

arrow_back 单调栈

可以发现如果要字典序最小,那么就需要让靠前的数字变小

那么最终形成的平均数是递增的

可以用单调栈维护平均数递增 ```cpp

include<bits/stdc++.h>

define gc

zc
2020-05-03 21:39

记录每个点左边和右边第一个比它小的,就可以求出它能的贡献区间

```cpp

include

include

include

include

zc
2019-12-21 19:47

维护两个单调递减栈,当i加进栈,位置x的数弹出的时候,在另一个栈中找到和这个数一样大的数,计算贡献(x-靠右左端点)\times (i-x) ```cpp

include<bits/

zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47
1 / 1
Search
search