P1904 天际线 <给别人的线段树代码注释一下>

#include <bits/stdc++.h>

using namespace std;
struct SGTree
{
	int le, ri;
	int la;
	int mx;
}t[40005];
struct Buildings
{
	int l, r;
	int h;
	bool operator <(const Buildings A) const
	{
		return h < A.h;
	}
}b[10005];
int a[10005];
void BuildT(int id, int l, int r)//建一个空树
{
	t[id].le = l;
	t[id].ri = r;
	t[id].la = 0;//lazy值为0
	if (t[id].le == t[id].ri)
	{
		t[id].mx = 0; //max默认为0，建的是空树
		return;
	}
	int mid = (l + r) / 2; 
	BuildT(id * 2, l, mid);
	BuildT(id * 2 + 1, mid + 1, r);
}
void Push(int id)//la标记下放
{
	if (t[id].la)
	{
		t[id * 2].la = t[id].la;//lazy值迭代左子叶
		t[id * 2 + 1].la = t[id].la; //迭代右子叶
		t[id * 2].mx = max(t[id * 2].mx, t[id * 2].la); 
		/* lazy值此处指更新后的值，无需再进行更改，然而
		为什么lazy值推到左右子叶后仍然能正常使用？---我看了，真的可以，因为change传入参数c固定*/
		t[id * 2 + 1].mx = max(t[id * 2 + 1].mx, t[id * 2 + 1].la);
		t[id].la = 0;
	}
}
void Change(int id, int l, int r, int c)//修改，注意细节
{
	if (t[id].le == l && t[id].ri == r)
	{
		t[id].mx = max(t[id].mx, c);
		t[id].la = c; //c是贯穿的常量，大概是把某个区间全数修改为int c，这就是模板
		return;
	}
	Push(id);//push向下推id到他的子叶，以保证子叶的值被更新，这样此id的值在上推时完全安全
	if (r <= t[id * 2].ri)
	{
		Change(id * 2, l, r, c); //二分递归查找
	}
	else if (l >= t[id * 2 + 1].le)
	{
		Change(id * 2 + 1, l, r, c);
	}
	else
	{
		Change(id * 2, l, t[id * 2].ri, c);
		Change(id * 2 + 1, t[id * 2 + 1].le, r, c);
	}
	t[id].mx = max(t[id * 2].mx, t[id * 2 + 1].mx);
}
int Query(int id, int l, int r)//查询
{
	if (t[id].le == l && t[id].ri == r)
	{
		return t[id].mx;
	}
	Push(id);
	if (r <= t[id * 2].ri)
	{
		return Query(id * 2, l, r);
	}
	else if (l >= t[id * 2 + 1].le)
	{
		return Query(id * 2 + 1, l, r);
	}
	else
	{
		return max(Query(id * 2, l, t[id * 2].ri), Query(id * 2 + 1, t[id * 2 + 1].le, r));
	}
}

int main()
{
	BuildT(1, 1, 10000);
	int l, h, r;
	int cnt = 1;
	while (cin >> b[cnt].l >> b[cnt].h >> b[cnt].r)
	{
		if (b[cnt].l == 0 && b[cnt].r == 0 && b[cnt].h == 0) /*效率极差*/
		{
			break;
		}
		cnt++;
	}
	sort(b + 1, b + cnt);//将高度排序，不然会错，我也不知道为什么
	for (int i = 1; i < cnt; ++i)
	{
		Change(1, b[i].l, b[i].r - 1, b[i].h); //只是维护线段树的操作而已。
		//你们省选选手都是些神经病，打个模拟还要线段树
	}
	for (int i = 1; i <= 10000; ++i)
	{
		a[i] = Query(1, i, i);//数据结构，到时候在查，这样的效率能高吗？
		printf("%d ", a[i]);
	}
	for (int i = 1; i <= 10000; ++i)
	{
		if (a[i] != a[i - 1])
		{
			printf("%d %d ", i, a[i]);//按照要求输出
		}
	}
	return 0;
}