UVA 1232 – SKYLINE（线段树区间更新）
最后更新于：2022-04-01 15:53:38
题目链接：[点击打开链接](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=502&page=show_problem&problem=3673)
题意：依次建n个建筑， 每个建筑有3个信息，宽度：[l, r]， 和高度h， 要求求出每个建筑刚建完时最高的部分的区间长度之和。
思路：就是维护线段树区间最值， 然而有一个问题， 因为不能更新比当前高度大的区间，所以最坏的情况下要更新到所有点， 因此要加一个懒惰标记，表示该区间是否被完全覆盖，覆盖值是多少。 另外由于是区间问题， 会产生区间端点的麻烦， 所以我们把线段树中的每一个点当作一个长度为1的区间， 比如i这个点， 当成是[i, i+1)这个区间。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000 + 7;
const int INF = 1000000000;
const int maxn = 100000 + 10;
int T,n,m,maxv[maxn<<2],setv[maxn<<2],ans;
struct node {
int l, r, h;
}a[maxn];
void PushUp(int o) {
maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
maxv[o] = 0;
setv[o] = 0;
if(l == r) return ;
build(l, m, o<<1);
build(m+1, r, o<<1|1);
}
void pushdown(int l, int r, int o) {
if(setv[o]) {
setv[o<<1] = setv[o<<1|1] = setv[o];
maxv[o<<1] = maxv[o<<1|1] = setv[o];
setv[o] = 0;
}
}
void update(int L, int R, int h, int l, int r, int o) {
int m = (l + r) >> 1;
if(setv[o] && maxv[o] > h) return ;
if(L <= l && r <= R) {
if(maxv[o] <= h) {
maxv[o] = h;
setv[o] = h;
ans += r - l + 1;
return ;
}
}
if(l == r) return ;
pushdown(l, r, o);
if(L <= m) update(L, R, h, l, m, o<<1);
if(m < R) update(L, R, h, m+1, r, o<<1|1);
PushUp(o);
}
int main() {
while(~scanf("%d",&T) && T) {
while(T--) {
scanf("%d",&n);
int m = 0;
for(int i=0;i<n;i++) {
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].h);
m = max(m, a[i].r);
}
build(1, m, 1);
ans = 0;
for(int i=0;i<n;i++) {
update(a[i].l, a[i].r-1, a[i].h, 1, m, 1);
}
printf("%d\n",ans);
}
}
return 0;
}
~~~