单调栈28pts 求救dalao
查看原帖
单调栈28pts 求救dalao
1125958
2010zrk楼主2025/7/27 11:34

找不到错误

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000000],ans,qq,b[1000000];
stack<long long>q;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];b[i]=1;}
	for(int i=n;i>=1;i--)
	{
		if(a[i]==a[i+1]){b[i]+=b[i+1];b[i+1]=1;}
	}
	for(int i=1;i<=n;i++)
	{	if(b[i]>1)ans+=(b[i]-1)*b[i]/2;
		if(q.empty()){q.push(i);}
		else
		{
			while(!q.empty()&&a[i]>a[q.top()])
			{//	long long tt=b[q.top()]+1;
				//long long t=q.top();
				ans+=b[q.top()];
			//	cout<<q.top()<<' '<<i<<' '<<ans<<endl;
				q.pop();
			}
			while(q.size()>0&&a[i]<a[q.top()])
			{//	long long tt=b[i]+b[q.top()];
				ans+=b[i];
			//	cout<<q.top()<<' '<<i<<' '<<ans<<endl;
				q.push(i);
			}
		//	if(!q.empty()&&a[i]<a[q.top()]){}
			if(q.empty()){q.push(i);}
		}
	}
	cout<<ans;
	return 0;
}

2025/7/27 11:34
加载中...