程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 1232 - SKYLINE(線段樹)

UVA 1232 - SKYLINE(線段樹)

編輯:C++入門知識

UVA 1232 - SKYLINE(線段樹)


UVA 1232 - SKYLINE

題目鏈接

題意:按順序建房,在一條線段上,每個房子一個高度,要求出每間房子建上去後的輪廓線

思路:線段樹延遲更新,一個setv作為高度的懶標記,此外還要在開一個cover表示當前結點一下是否都為同一高度

代碼:

#include 
#include 
#include 
using namespace std;

#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)

const int N = 100005;

int t, n;

struct Node {
    int l, r, h, setv;
    bool cover;
    Node() {}
    Node(int l, int r) {
	this->l = l; this->r = r;
	h = 0; setv = 0; cover = true;
    }
} node[4 * N];

void pushup(int x) {
    node[x].cover = ((node[lson(x)].h == node[rson(x)].h) && node[lson(x)].cover && node[rson(x)].cover);
    node[x].h = node[lson(x)].h;
}

void pushdown(int x) {
    node[lson(x)].setv = max(node[lson(x)].setv, node[x].setv);
    node[rson(x)].setv = max(node[rson(x)].setv, node[x].setv);
    node[lson(x)].h = max(node[lson(x)].setv, node[lson(x)].h);
    node[rson(x)].h = max(node[rson(x)].setv, node[rson(x)].h);
}

void build(int l, int r, int x = 0) {
    node[x] = Node(l, r);
    if (l == r) return;
    int mid = (l + r) / 2;
    build(l, mid, lson(x));
    build(mid + 1, r, rson(x));
}

int query(int l, int r, int v, int x = 0) {
    if (node[x].cover && node[x].h > v) return 0;
    if (node[x].l >= l && node[x].r <= r && node[x].cover) {
	node[x].setv = v;
	node[x].h = v;
	return node[x].r - node[x].l + 1;
    }
    int mid = (node[x].l + node[x].r) / 2;
    int ans = 0;
    pushdown(x);
    if (l <= mid) ans += query(l, r, v, lson(x));
    if (r > mid) ans += query(l, r, v, rson(x));
    pushup(x);
    return ans;
}

int main() {
    scanf("%d", &t);
    while (t--) {
	scanf("%d", &n);
	build(1, N - 1);
	int l, r, h;
	int ans = 0;
	while (n--) {
	    scanf("%d%d%d", &l, &r, &h);
	    ans += query(l, r - 1, h);
	}
	printf("%d\n", ans);
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved