bzoj1113:[Poi2008]海报PLA

传送门

sb单调栈，唯一要注意的是高度相同的时候不需要更新答案
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
	char ch; bool ok;
	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=2.5e5+10;
int n,a[maxn],st[maxn],top,ans;
int main()
{
	read(n);
	for(rg int i=1,j;i<=n;i++)read(j),read(a[i]);
	for(rg int i=1;i<=n;i++)
	{
		while(a[i]<=st[top])ans+=a[i]==st[top]?0:1,top--;
		st[++top]=a[i];
	}
	ans+=top;
	printf("%d
",ans);
}