UVA1232 - SKYLINE(段树部分的变化)

时间:2023-01-30 10:49:23

UVA1232 - SKYLINE(线段树区间改动)

题目链接

题目大意:依照顺序盖楼。假设这个位置(当前要盖的楼覆盖范围内)要新建的楼的高度>=之前就有的最大高度,那么就+1.最后输出这个+1的总数。

解题思路:线段树区间改动值,而且每次改动的时候返回改动的位置总数。

由于可能左右子树的高度会有不同。所以这里增加一个sign来表示左右这一段是否高度一致。

代码:

#include <cstdio>
#include <cstring> const int maxn = 1e5 + 5; #define lson(x) ((x)<<1)
#define rson(x) (((x)<<1) + 1) struct Node { int l, r, h, sign;
void set (int l, int r, int h, int sign) { this->l = l;
this->r = r;
this->h = h;
this->sign = sign;
}
}node[4 * maxn]; void pushdown(int u) { node[lson(u)].sign = node[rson(u)].sign = 1;
node[lson(u)].h = node[rson(u)].h = node[u].h;
node[u].sign = 0;
node[u].h = 0;
} void pushup (int u) { node[u].l = node[lson(u)].l;
node[u].r = node[rson(u)].r; if (node[lson(u)].sign && node[rson(u)].sign && node[lson(u)].h == node[rson(u)].h) { node[u].sign = 1;
node[u].h = node[lson(u)].h;
} else
node[u].sign = node[u].h = 0;
} void build (int u, int l, int r) { if (l == r)
node[u].set(l, r, 0, 1);
else { int m = (l + r) / 2;
build(lson(u), l, m);
build(rson(u), m + 1, r);
pushup(u);
}
} int update (int u, int l, int r, int h) { if (node[u].sign && node[u].h > h)
return 0; if (node[u].l >= l && node[u].r <= r && node[u].sign) { node[u].h = h;
return node[u].r - node[u].l + 1;
} int ret = 0;
int m = (node[u].l + node[u].r) / 2; if (node[u].sign)
pushdown(u); if (l <= m)
ret += update (lson(u), l, r, h);
if (r > m)
ret += update (rson(u), l, r, h);
pushup(u); return ret;
} int main () { int T;
int n, l, r, h, ans; scanf ("%d", &T); while (T--) { build(1, 1, maxn);
scanf ("%d", &n); ans = 0;
for (int i = 0; i < n; i++) { scanf ("%d%d%d", &l, &r, &h);
ans += update (1, l + 1, r, h);
} printf ("%d\n", ans);
}
return 0;
}