P1904 天际线

using namespace std;
struct node {
	int l, r, h;
}building[5001];


int height[5001];


int main()
{
	int n = 1;
	while (cin>>building[n].l>>building[n].h>>building[n].r) n++;
	n--;
	int i;
	int maxr = 0;
	for (i = 1; i <= n; i++)
	{
		for (int j = building[i].l; j < building[i].r; j++)

			if (building[i].h > height[j]) height[j] = building[i].h;

		if (maxr < building[i].r) maxr = building[i].r;

	}

	for (int j = 1; j <= maxr; j++)
		if (height[j] != height[j - 1]) cout << j << " " << height[j] << " ";
	return 0;
}
//
//14ms /  688.00KB /  570B C++

　　小心此题为线段而不是单个的点，我吧0~1，1~2……的区间收束为单个的点，比如0~1为0，1~2为1，

假定13~14的区间突然升高了高度，那就输出(13,h)。

时间复杂度为O(n)，折点的高度相较先前的点发生了变化，如果不一样就输出。

我搞不懂这题为什么是提高+，省选-。还要用线段树？

其实只需要暴力模拟就可以AC了。

至于能不能简化到O（logn)，等我下午把线段树学了再试一下。