Codechef Sam and Sequences（单调队列）

本文主要是介绍Codechef Sam and Sequences（单调队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:http://www.codechef.com/problems/PRYS03/

这题只要考虑每个数字，最左和最右分别能延伸到的位置，然后就能计算出每个数字需要计算的次数，由于数字可能重复，所以对于左边维护到不大于的第一个数字位置，右边维护到小于的第一个数字位置，然后维护好后，在扫一遍计算总和即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int N = 100005;int t, n;
ll a[N];struct Node {ll v;int id;Node() {}Node (ll v, int id) {this->v = v;this->id = id;}
} S[N];int left[N], right[N];int main() {scanf("%d", &t);while (t--) {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);S[0].id = 0;int top = 0;for (int i = 1; i <= n; i++) {while (top && S[top].v > a[i]) top--;left[i] = S[top].id;S[++top] = Node(a[i], i);}S[0].id = n + 1;top = 0;for (int i = n; i >= 1; i--) {while (top && S[top].v >= a[i]) top--;right[i] = S[top].id;S[++top] = Node(a[i], i);}ll ans = 0;for (int i = 1; i <= n; i++)ans += (ll)(i - left[i]) * (right[i] - i) * a[i];printf("%lld\n", ans);}return 0;
}

这篇关于Codechef Sam and Sequences（单调队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---