BZOJ 1683.City skyline 城市地平線

傳送門

從左到右掃一遍，考慮什么時候會和之前形成同一幢房子從而不用統計

顯然是當前的高度和之前某個點高度相同，并且它們之間沒有更矮的建筑

考慮用一個單調棧維護一個單調上升的房子輪廓，然后對于掃到的每一個高度，看看棧里有沒有相同的高度就行了

但是我比較傻逼，沒想到，所以用 $set$ 去維護單調棧就可以維護的東西...

每個位置進出 $set$ 一次，復雜度 $O(n \log n)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
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<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f;
}
const int N=5e5+7;
int n,m,ans;
set <int> S;
set <int>::iterator it,pit;
int main()
{n=read(),m=read();int x,y; S.insert(0);for(int i=1;i<=n;i++){x=read(),y=read();for(it=S.upper_bound(y);it!=S.end();it=S.upper_bound(y)) S.erase(it);if(S.find(y)==S.end()) { ans++; S.insert(y); }}printf("%d\n",ans);return 0;
}

?