阅读量:0
思路：单调栈（分别统计左边小于等于当前大小的数量）
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef pair<int, int> pii; typedef pair<ll, ll> PII; #define pb emplace_back //#define int ll #define all(a) a.begin(),a.end() #define x first #define y second #define ps push_back #define endl '\n' #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) void solve(); const int N = 1e6 + 10; signed main() { IOS; solve(); return 0; } void solve() { ll n; cin >> n; vector<ll> a(n+1),ans1(n+1,0),ans2(n+1,0); stack<ll> st; for(int i = 1; i <= n; ++ i) cin >> a[i]; for(int i = 1; i <= n; ++ i) { while(st.size() && st.top() > a[i]) st.pop(); ans1[i] = st.size(); st.push(a[i]); } while(st.size()) st.pop(); for(int i = n; i >= 1; -- i) { while(st.size() && st.top() > a[i]) st.pop(); ans2[i] = st.size(); st.push(a[i]); } for(int i = 1; i <= n; ++ i) cout << ans1[i] + ans2[i] << " \n"[i==n]; }