Skyscrapers (hard version) | 分治+线段树

-题目：
http://codeforces.com/contest/1313/problem/C2
-分析:
一开始一直在往最高点方面想，题解的方向是最低点。。。巧妙地避开了答案
考虑分治的做法，对于当前的区间，找出最小值点u（线段数预处理一波。。）。由于u两侧一定有一侧会跟u的值一样，所以两边都分治一下，然后更新res[]；
-代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp(a, b) make_pair(a, b)
//typedef __int128 lll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define fi first
#define se second
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
typedef pair<long long, int> par;
struct node
{
	int l, r;
	par minn;
}t[maxn << 2];
int n;
ll a[maxn], res[maxn];

void pushup(int tar)
{
	if(t[tar << 1].minn.fi < t[tar << 1 | 1].minn.fi) t[tar].minn = t[tar << 1].minn;
	else t[tar].minn = t[tar << 1 | 1].minn;
}

void build(int l, int r, int tar)
{
	t[tar].l = l, t[tar].r = r;	
	if(l == r)
	{
		t[tar].minn = mp(a[l], l);
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, tar << 1), build(mid + 1, r, tar << 1 | 1);
	pushup(tar);
}

par query(int l, int r, int tar)
{
	if(t[tar].l == l && t[tar].r == r) return t[tar].minn;
	int mid = t[tar].l + t[tar].r >> 1;
	if(r <= mid) return query(l, r, tar << 1);
	else if(l > mid) return query(l, r, tar << 1 | 1);
	else return min(query(l, mid, tar << 1), query(mid + 1, r, tar << 1 | 1));
}

ll solve(int l, int r)
{
	if(l > r) return 0ll;
	if(l == r)
	{
		res[l] = a[l];
		return res[l];
	}
	par min = query(l, r, 1);
	ll suml = solve(l, min.se - 1), sumr = solve(min.se + 1, r);
	ll lenl = min.se - l, lenr = r - min.se;
	if(suml + min.fi + lenr * min.fi > sumr + min.fi + lenl * min.fi) 
	{
		for(int i = min.second; i <= r; i++) res[i] = min.first;
		return suml + min.fi + lenr * min.fi;
	}
	else
	{
		for(int i = l; i <= min.second; i++) res[i] = min.first;
		return sumr + min.fi + lenl * min.fi;
	}
}

int main()
{
	//close();
	cin >> n;
	for(int i = 1; i <= n; i++)
		scanf("%lld", a + i);
	build(1, n, 1);
	///cout << query(1, n - 1, 1).first << " " << query(1, n - 1, 1).second << endl;
	solve(1, n);
	for(int i = 1; i <= n; i++)
		printf("%lld%c", res[i], i == n ? '\n' : ' ');
}