Zerojudge c364 我鄙視你

題目

https://zerojudge.tw/ShowProblem?problemid=c364

給你一個序列，問你第ii個值往右看和往左看直到碰到≥\ge他的值就停下來，然後計算這些數字的總和

Solution

做兩次單調Stack，分別是從右到左跟從左到右

由於第ii個值碰到≥\ge他的值就會停下來，我們假設這個值叫做aja_j，則ai,aj,...a_i,a_j,...可以觀察出一個遞增或遞減的單調性，而區間(i,j)(i,j)之間的值就是被aia_i或aja_j所鄙視的值(根據是右到左做單調Stack還是左到右做來決定區間內的值要被誰鄙視)

用ans1,ans2ans1,ans2分別儲存每個值往左鄙視跟往右鄙視的總和，最後輸出再把他們加總起來就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/extc++.h>
#include <bits/stdc++.h>
#pragma gcc optimize("ofast,unroll-loops,no-stack-protector,fast-math")
#pragma gcc target("abm,bmi,bmi2,mmx,sse,sse2,sse3,ssse3,sse4,popcnt,avx,avx2,fma,tune=native")
#pragma comment(linker, "/stack:200000000")
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define double long double
#define pb push_back
#define sz(x) (int)(x).size()
#define all(v) begin(v),end(v)
#define debug(x) cerr<<#x<<" = "<<x<<'\n'
#define LINE cout<<"\n-----------------\n"
#define endl '\n'
#define VI vector<int>
#define F first
#define S second
#define MP(a,b) make_pair(a,b)
#define rep(i,m,n) for(int i = m;i<=n;++i)
#define res(i,m,n) for(int i = m;i>=n;--i)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define Case() int _;cin>>_;for(int Case = 1;Case<=_;++Case)
#define pii pair<int,int>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
template <typename K, typename cmp = less<K>, typename T = thin_heap_tag> using _heap = __gnu_pbds::priority_queue<K, cmp, T>;
template <typename K, typename M = null_type> using _hash = gp_hash_table<K, M>;
template <typename K, typename M = null_type, typename cmp = less<K>, typename T = rb_tree_tag> using _tree = tree<K, M, cmp, T, tree_order_statistics_node_update>;
template <typename K, typename M = null_type, typename cmp = less_equal<K>, typename T = rb_tree_tag> using _multitree = tree<K, M, cmp, T, tree_order_statistics_node_update>;
const int N = 1e6+5,L = 20,mod = 1e9+7,inf = 1e9+7;
const double eps = 1e-7;
void solve(){
	int n;cin>>n;
	VI v(n),ans1(n),ans2(n);
	stack<int>st1,st2;
	for(int i = 0;i<n;++i){
		cin>>v[i];
	}
	for(int i = 0;i<n;++i){
		while(!st1.empty() and v[st1.top()]<v[i]){
			ans1[i]+=v[st1.top()];
			ans1[i]+=ans1[st1.top()];
			st1.pop();
		}
		st1.push(i);
	}
	for(int i = n-1;i>=0;--i){
		while(!st2.empty() and v[st2.top()]<v[i]){
			ans2[i]+=v[st2.top()];
			ans2[i]+=ans2[st2.top()];
			st2.pop();
		}
		st2.push(i);
	}
	rep(i,0,n-1){
		cout<<ans1[i]+ans2[i]<<endl;
	}
}
signed main(){
	IOS;
	solve();
}