abc372 C\D
D.独立想出来的。前缀和+单调栈
#include <bits/stdc++.h>
#include <set>
using namespace std;
const int N = 200005;
int h,n,a[N],sum[N],s[N];
stack<int> q;
//降序
//5 3 1 4
//5 3 1 6
//2
//1 2 3 4
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
for(int i = 1; i <= n; i++){
cin>>a[i];
while(!q.empty() && a[i] > a[q.top()]) q.pop();
if(!q.empty()) h = q.top();
else h = 1;//栈为空
if(i != h) s[h]++,s[i]--;
q.push(i);
}
for(int i = 1; i <= n; i++){
sum[i] += sum[i-1] + s[i];
cout<<sum[i]<<" ";
}
return 0;
}
/*
5
% 2 1 4 3 5
*/