专栏文章

题解：UVA1232 SKYLINE

BBobi2014
UVA1232题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minovwg0
此快照首次捕获于
2025/12/02 05:56
3 个月前
此快照最后确认于
2025/12/02 05:56
3 个月前
查看原文
这是一道可癌的线段树题。

前置知识

思路

考虑使用线段树存储区间最小高度、区间最大高度，注意懒标记要赋值为 −1-1，看完后面的内容你就知道为什么要赋值为 −1-1 了。build 代码如下：
CPP
void build(int p,int l,int r){
	tri[p].l = l,tri[p].r = r,tri[p].tag = -1;
	tri[p].minn = tri[p].maxx = 0;
	if(l == r){	
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1,l,mid);
	build(p << 1 | 1,mid + 1,r);
}
每次查询时如果区间的最小值已经比这个建筑的高度要高了，那么直接 return，如果这个区间再范围内且最大值小于等于这个建筑的高度，那么把答案加上区间长度，并且将区间全部赋值为这个建筑的高度。pushdown 函数如下：
CPP
void pushdown(int p){
	if(tri[p].tag != -1){
		tri[p << 1].tag = tri[p].tag;
		tri[p << 1 | 1].tag = tri[p].tag;
		tri[p << 1].minn = tri[p].tag;
		tri[p << 1 | 1].minn = tri[p].tag;
		tri[p << 1].maxx = tri[p].tag;
		tri[p << 1 | 1].maxx = tri[p].tag;
		tri[p].tag = -1;
	}
}
查询函数的其他部分就和普通的区间查询一样了，注意如果区间在范围内但是最大值比建筑的高度大，那么不能 return 要继续递归。query 函数与 update 的函数的结合体如下：
CPP
void update(int p,int l,int r,int val){
	if(tri[p].minn > val){
		return;
	}
	if(tri[p].l >= l and tri[p].r <= r){
		if(tri[p].maxx <= val){
			tri[p].minn = val;
			tri[p].maxx = val;
			tri[p].tag = val;
			ans += (tri[p].r - tri[p].l + 1);
			return;
		}
	}
	pushdown(p);
	int mid = (tri[p].l + tri[p].r) >> 1;
	if(l <= mid){
		update(p << 1,l,r,val);
	}
	if(r > mid){
		update(p << 1 | 1,l,r,val);
	}
	tri[p].minn = min(tri[p << 1].minn,tri[p << 1 | 1].minn);
	tri[p].maxx = max(tri[p << 1].maxx,tri[p << 1 | 1].maxx);
}
最后提醒一下：
多测不清空，爆零两行泪。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int T,Q,ans;
namespace SegmentTree{
	struct node{
		int l,r,minn,maxx,tag;
	} tri[(N << 2) + 5];
	void build(int p,int l,int r){
		tri[p].l = l,tri[p].r = r,tri[p].tag = -1;
		tri[p].minn = tri[p].maxx = 0;
		if(l == r){	
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1,l,mid);
		build(p << 1 | 1,mid + 1,r);
	}
	void pushdown(int p){
		if(tri[p].tag != -1){
			tri[p << 1].tag = tri[p].tag;
			tri[p << 1 | 1].tag = tri[p].tag;
			tri[p << 1].minn = tri[p].tag;
			tri[p << 1 | 1].minn = tri[p].tag;
			tri[p << 1].maxx = tri[p].tag;
			tri[p << 1 | 1].maxx = tri[p].tag;
			tri[p].tag = -1;
		}
	}
	void update(int p,int l,int r,int val){
		if(tri[p].minn > val){
			return;
		}
		if(tri[p].l >= l and tri[p].r <= r){
			if(tri[p].maxx <= val){
				tri[p].minn = val;
				tri[p].maxx = val;
				tri[p].tag = val;
				ans += (tri[p].r - tri[p].l + 1);
				return;
			}
		}
		pushdown(p);
		int mid = (tri[p].l + tri[p].r) >> 1;
		if(l <= mid){
			update(p << 1,l,r,val);
		}
		if(r > mid){
			update(p << 1 | 1,l,r,val);
		}
		tri[p].minn = min(tri[p << 1].minn,tri[p << 1 | 1].minn);
		tri[p].maxx = max(tri[p << 1].maxx,tri[p << 1 | 1].maxx);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T --){
		cin >> Q;
		SegmentTree::build(1,1,N);
		ans = 0;
		while(Q --){
			int l,r,h;
			cin >> l >> r >> h;
			SegmentTree::update(1,l,r - 1,h);
		}
		cout << ans << '\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...