开发笔记:Codeforces1313C.Skyscrapers

篇首语：本文由编程笔记#小编为大家整理，主要介绍了Codeforces 1313C.Skyscrapers相关的知识，希望对你有一定的参考价值。

题目链接

题意是给你一个数组，问你如何建造，使得每个点都不小于其左右的点，包括不相邻的点

分析题意，容易得知，就是找一个点两侧的不上升序列且带修，那我们就分别从头跑一遍，从尾跑一遍，两者相加就是每个点的最大值

那我们可以利用单调栈来进行这个操作，注意初始化栈

这道题和CF1300E思想一样，都是用单调栈求最大不下降序列的和值，且可以进行修改

#include
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
typedef pair pii;
const int maxn = 500003;
int buf[maxn], q[maxn];
LL s[maxn];
void run_case() {
int n; cin >> n;
for(int i = 1; i <= n; ++i) cin >> buf[i];
LL sum = 0;
int top = 0;
q[0] = 0; // init stack
for(int i = 1; i <= n; ++i) {
while(top && buf[i] int now = q[top--];
sum -= 1LL * (now - q[top]) * buf[now];
}
sum += 1LL * (i - q[top]) * buf[i];
s[i] += sum;
q[++top] = i;
}
sum = 0, top = 0;
q[0] = n+1; // init stack
for(int i = n; i >= 1; --i) {
while(top && buf[i] int now = q[top--];
sum -= 1LL * (q[top] - now) * buf[now];
}
sum += 1LL * (q[top] - i) * buf[i];
s[i] += sum - buf[i];
q[++top] = i;
}
int pos = max_element(s+1, s+1+n) - s;
for(int i = pos-1; i >= 1; --i)
buf[i] = min(buf[i], buf[i+1]);
for(int i = pos+1; i <= n; ++i)
buf[i] = min(buf[i], buf[i-1]);
for(int i = 1; i <= n; ++i)
cout <}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cout.flags(ios::fixed);cout.precision(10);
//int t; cin >> t;
run_case();
cout.flush();
return 0;
}

求一个点两边的性质可以跑两遍来实现