——接上一篇题解，【洛谷】【单调栈】P1823音乐会的等待

关于题目大意在上一篇题解里已经说清楚了，这里不再多阐述

想看题目->戳这里




[算法分析：]

在对元素a进行判断时，如果它与栈顶元素相等，累加答案pop栈顶元素，在最后再把pop掉的相同的栈顶元素push进来

这样一个一个操作好慢啊！

可以有一种比较显著的优化：

记录每一种元素的值的同时记录它们的个数，这样在有相同元素的时候就不必一个一个pop累加再push而是可以直接累加上所有相同的元素.

同时相同的元素不必再进栈而是只用把栈顶（用deque的话是队尾）元素的个数加一.




\([Code:]\)

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long LL;

const int MAXN = 500000 + 1;

int n;

struct Node {

	int v, num;

};

deque<Node> q;

inline int read() {

    int x=0, f=1; char ch=getchar();

    while(ch<'0' || ch>'9') {

        if(ch == '-') f = -1;

        ch = getchar();

    }

    while(ch>='0' && ch<='9')

        x=(x<<3)+(x<<1)+ch-48, ch=getchar();

    return x * f;

}

int main() {

	n = read();

	LL ans = 0;

	for(int i=1; i<=n; ++i) {

		int a = read();

		while(!q.empty() && q.back().v<a) {

			ans += q.back().num;

			q.pop_back();

		}

		if(!q.empty() && q.back().v == a) {

			if(q.size() > 1) ++ ans;

			ans += q.back().num;

			++q.back().num;

		}

		else {

			if(!q.empty()) ++ans;

			q.push_back((Node){a, 1});

		}

	}

	printf("%lld\n", ans);

}