P1823 [COI2007] Patrik 音乐会的等待

标签：node COI2007 int long tail 500001 Patrik P1823

用单调队列维护即可，注意要考虑高度相同的情况（可以记录单调队列中相同的个数）。

时间复杂度为 \(O(n)\) 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
	int x,y;
}q[500001];
int a[500001];
int head=1,tail=0,x,ans;
signed main()
{
	cin>>n>>a[1];
	q[++tail]=(node){a[1],1};
	for(int i=2; i<=n; i++)
	{
		cin>>a[i];
		int res=0,num=1;
		while(head<=tail&&q[tail].x<=a[i])
		{
			res+=q[tail].y;
			if(q[tail].x==a[i])num+=q[tail].y;
			tail--;
		}
		if(head<=tail)res++;
		ans+=res;
		q[++tail]=(node){a[i],num};
	}
	cout<<ans<<endl;
	return 0;
}

标签：node,COI2007,int,long,tail,500001,Patrik,P1823
From： https://www.cnblogs.com/dadidididi/p/16756325.html