【RQNOJ】460 诺诺的队列

借用曾经的做法，求出来的东西相对于全部看得到的数对，对于全部a[i]相等的看得见的数对，仅仅算了一次。

于是事实上每次高过别人的时候操作仅仅要加上s(a[i])，第一次比别人矮的时候加上1而不是s(a[i])。

把栈内的东西给扩充，不仅存元素。还存个数，这样就攻克了。

单调栈代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int N=500001;

struct Stack
{
	int w,c;
}stk[N];
int size;
int n,w[N],cnt;

inline int read(void)
{
	int s=0,f=1; char c=getchar();
	for (;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;
	for (;'0'<=c&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
	return s*f;
}

int main(void)
{	
	n=read();
	for (int i=1;i<=n;i++) w[i]=read();
	
	for (int i=1;i<=n;i++)
	{
		for (;size&&stk[size].w<w[i];size--)
		{
			cnt+=stk[size].c;
			stk[size].w=stk[size].c=0;
		}
		if (size&&stk[size].w==w[i])
		{
			cnt+=stk[size].c;
			stk[size].c++;
			if (size-1) cnt++;
		}
		else
		{
			if (size) cnt++;
			stk[++size].w=w[i];
			stk[size].c=1;
		}
	}
	printf("%d\n",cnt);
	
	return 0;
}