2022省赛选拔 D(单调栈)

题目 题意: 给定长度为n的数组，可以执行任意次operation，最后输出字典序最小的数组。 operation: 选定数组任意子区间，让每个数变成该区间的平均值。 思路: 一种朴素的想法是迭代，如果一个序列是非递减的，取平均不会更优。所以每遇到严格递减的序列，就取平均。之后一直迭代。但是这种做法有点暴力，会被卡掉。 更优秀的做法是二分或者单调栈。 单调栈始终维护一个上升序列，当新遇到的元素小于栈顶时，就一直弹栈，并将两块数合并变成平均值，直到变为单调不减的序列。 时间复杂度: O(n) 代码:

// Problem: C. Water Balance
// Contest: Codeforces - Codeforces Round #618 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1299/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i 1)
	{
		if(st[top]