[TIOJ] 1202. 重疊的天際線

題目連結:http://tioj.infor.org/problems/1202

---

一開始看到的時候總覺得線段樹可以秒過，不過想說應該不需要，應該有線性的作法，所以這題我一直以為是某種單調隊列，直到我想了超久後才發現他無法好好維護單調性的(或者說他沒有單調性)，因此原本要回去刻線段樹，越刻越覺得操作很神奇，仔細想想後才發現自己根本在寫heap，把他想成heap之後就很簡單了XD。
就先把過期的建築拔掉，再把每棟建築依照左界丟進去，之後得到最大的高度，最後再取個unique即可。

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 30000 + 5;

struct BB{
	int l, r, h;
	bool operator<(const BB& x)const{
		return h<x.h;
	}
};
vector<BB> buildings;
vector<int> points;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n, n){
		points.clear();
		buildings.clear();
		for(int i=0;i<n;i++){
			int a,b,c; cin>>a>>b>>c;
			buildings.PB({a,c,b});
			points.PB(a);
			points.PB(c);
		}
		buildings.PB({1, 1000000001, 0});
		sort(ALL(buildings), [](const BB& a, const BB& b){return a.l < b.l;});
		queue<BB> qq;
		for(auto i:buildings) qq.push(i);
		sort(ALL(points));
		points.resize(distance(points.begin(), unique(ALL(points))));
		priority_queue<BB> pq;
		vector<PII> ans;
		for(auto i:points){
			while(!pq.empty() and pq.top().r <= i) pq.pop();
			while(!qq.empty() and qq.front().l <= i){
				pq.push(qq.front());
				qq.pop();
			}
			ans.PB({i, pq.top().h});
		}
		ans.resize(distance(ans.begin(), \
			 unique(ALL(ans), [](const PII &a, const PII &b){return a.SS == b.SS;})\
			 ));
		for(auto it=ans.begin();\
			cout<<((it==ans.end() or it==ans.begin())?"":" "), \
			it!=ans.end();\
			it++)
			cout<<it->FF<<" "<<it->SS;
		cout<<'\n';
	}
	return 0;
}