不⚡乘⚡的⚡单⚡调⚡栈⚡解

题目提示要用归并排序，易得本蒟蒻根本不会qwq，但是整了一个猎奇的单调栈解法qwq

时间复杂度：$O(n)$

思路

维护一个单调栈，优化时间复杂度。

遍历目标数组，维护一个单调栈：

1. 循环
   1. 栈不为空，且栈顶元素小于x：出栈，待下一轮查看栈顶元素是否满足要求。（继续循环）
   2. 不满足 1 的条件：结束循环。
2. 循环结束。
   1. 栈不为空：找到了第一个满足条件的元素，输出栈顶元素。
   2. 栈为空：没有满足要求的元素，输出-1.
3. 将x入栈：要么栈顶元素小于x，要么栈为空，两种情况都可以继续维护单调栈。

代码

#include<bits/stdc++.h>
using namespace std;

long long n,sum,ans; //回看 sum 似乎能用 i-1 代替qwq
stack<int> stk;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,res=0;
		
		cin>>x;
		
		while(!stk.empty()&&stk.top()>=x){
			res++;
			stk.pop();
		}
		if(!stk.empty()) ans+=sum-res; 
		
		stk.push(x);
		sum++;
	}
	
	cout<<ans;
	
	return 0;
}