UVa 1232 SKYLINE (线段树区间修改）

     大意：有一个序列，开始时全为零。现有一些操作，将区间[l,r)上小于等于c的数全部改为c，求总修改次数。

     思路：很容易想到考查的是线段树区间修改，怎么做呢，其实只要对线段树模板的边界代码稍微修改下即可。在进行更新时，如果待更新区间覆盖了当前区间，那么这个当前区间有三种情况：还未进行过赋值（即全为0，这时的标记为-1）、已经进行过赋值但没有更新到子结点（此时的标记即为c）、已经进行过赋值并以更新到子结点（这时的标记为-2）。

     对于第一种情况，直接赋值并更新答案即可；第二种也类似，如果c大于等于当前的标记则赋值并更新答案；而第三种，由于并不知道子结点的具体数值，所以要继续向下递归。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn = 100000 + 5;
int setv[maxn<<2],minv[maxn<<2],ans;
void PushUp(int rt)
{
minv[rt] = min(minv[rt<<1],minv[rt<<1|1]);
}
void PushDown(int rt)
{
if (setv[rt] >= 0) {
setv[rt<<1] = setv[rt<<1|1] = setv[rt];
minv[rt<<1] = minv[rt<<1|1] = setv[rt];
setv[rt] = -2;
}
}
void build(int l, int r, int rt)
{
if (l == r) {
setv[rt] = -1;
minv[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int ql, int qr, int h, int l, int r, int rt)
{
if (minv[rt] > h) return;
if (ql <= l && r <= qr) {
if (h >= setv[rt] && setv[rt] != -2) {
ans += r-l+1;
setv[rt] = minv[rt] = h;
return;
}
}
PushDown(rt);
int m = (l + r) >> 1;
if (ql <= m) update(ql,qr,h,lson);
if (m < qr) update(ql,qr,h,rson);
PushUp(rt);
}
int main()
{
int T;
scanf("%d",&T);
while(T--) {
build(1,maxn,1);
setv[1] = 0;
ans = 0;
int n;
scanf("%d",&n);
while(n--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b-1,c,1,maxn,1);
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是奋斗大炮为你收集整理的UVa 1232 SKYLINE (线段树区间修改）的全部内容，希望文章能够帮你解决UVa 1232 SKYLINE (线段树区间修改）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。