---

title: poj-2528線段樹練習(xí)
date: 2018-10-13 13:45:09
tags:

• acm
• 刷題
  categories:

• ACM-線段樹

概述

這道題坑了我好久啊啊啊啊，，，，

到現(xiàn)在也只是理解了kaungbin的代碼，，，知道每一步做什么，，，但感覺就是哪里有些不對勁的樣子，，，，

這道題有兩個點(diǎn)是我感覺很重要的，，，一個是數(shù)據(jù)的離散化，，，另一個是線段樹的變形，，，也就是它所維護(hù)的東西和之前見過的不一樣了，，，，

分析思路

題意是這樣的，，，在一個很大的區(qū)間里，，，不停的給每一個區(qū)間覆蓋海報(bào)，，，每個覆蓋的海報(bào)是不一樣的，，然后問你最后一共有幾個海報(bào)是露出來的，，，

大體上的思路是與所給貼海報(bào)相反的順序貼海報(bào)，，，這樣的話第一張（也就是原來順序的最后一張）一定是全露出來的，，然后第二張（也就是原來順序的倒數(shù)第二張）如果是在第一張的區(qū)間里說明它就被完全覆蓋了，，如果是在第一張以外的其他地方，，，就說明這張也一定是露出來的，，，以此類推，，對于每一次判斷出是露出來的++ans，，，最終全處理了就得到了答案，，，數(shù)據(jù)要離散后再用，，，

可以看出這樣的寫法中線段樹只是用來判斷每一次的貼海報(bào)，，，也就是說，，，線段樹只是用來維護(hù)每一個區(qū)間是否被覆蓋（更新），，，同時返回所要覆蓋的區(qū)間是否有露出來的（查詢），，，所以更新和查詢的操作可以合并在一起，，，，

實(shí)現(xiàn)

數(shù)據(jù)的離散化

先說一下離散怎么實(shí)現(xiàn):

首先原數(shù)據(jù)保存到x[maxn]數(shù)組，，，

然后把所有的數(shù)據(jù)復(fù)制到另一個數(shù)組a[maxn]，，，

對其排序，，，

去重，，，

然后對去重的數(shù)組a[maxn]遍歷進(jìn)行離散，，，

這樣想要知道知道原來數(shù)據(jù)中x所對應(yīng)離散后的位置就為hash[x]，，，

sort(a , a + count); count = unique(a , a + count) - a; for(int i = 0; i < count; ++i)hash[a[i]] = i;

最后的代碼

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring>using namespace std; #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r const int maxn = 1e5 + 10; struct node {int l;int r;bool cov; //表示這個節(jié)點(diǎn)所代表的區(qū)間是否被覆蓋 }node[maxn << 2];struct poster //表示海報(bào)的結(jié)構(gòu)體 {int l;int r; }poster[maxn << 2];void build(int rt , int l , int r) {node[rt].l = l;node[rt].r = r;node[rt].cov = false; //每一個區(qū)間初始化為未覆蓋if(l == r) return;int mid = (l + r) >> 1;build(lson);build(rson); }bool post(int rt , int l , int r) {//當(dāng)前節(jié)點(diǎn)，所要覆蓋的額區(qū)間[l , r]if(node[rt].cov) return false; //若這個區(qū)間已經(jīng)被覆蓋直接返回if(node[rt].l == l && node[rt].r == r){node[rt].cov = true; //未覆蓋的前提下找到整個區(qū)間時return true;}bool res;int mid = (node[rt].l + node[rt].r) >> 1;if(r <= mid) res = post(rt << 1 , l , r);else if(l > mid)res = post(rt << 1 | 1 , l , r);else{bool r1 = post(rt << 1 , l , mid);bool r2 = post(rt << 1 | 1 , mid + 1 , r);res = r1 || r2; //當(dāng)跨兩個區(qū)間時，，，要分別判斷是否都是被覆蓋的，，有一個沒覆蓋即露出就說明這個區(qū)間有露出的}if(node[rt << 1].cov && node[rt << 1 | 1].cov) //兩個子區(qū)間都露出父節(jié)點(diǎn)也是露出node[rt].cov = true;return res; }int a[maxn]; int hash[10000010];int main() {int T;scanf("%d" , &T);while(T--){int n;scanf("%d" , &n);int count = 0;for(int i = 0; i < n; ++i){scanf("%d%d" , &poster[i].l , &poster[i].r);a[count++] = poster[i].l;a[count++] = poster[i].r;//相鄰存點(diǎn)}//離散sort(a , a + count);count = unique(a , a + count) - a;for(int i = 0; i < count; ++i)hash[a[i]] = i;build(1 , 0 , count - 1);int ans = 0;for(int i = n - 1; i >= 0; --i) //反著遍歷，，有露出的就增一if(post(1 , hash[poster[i].l] , hash[poster[i].r]))++ans;printf("%d\n" , ans);} }//一個缺點(diǎn)，，，這樣單純的離散數(shù)據(jù)會出錯，，，像這一組，，， //但是poj上沒有考慮這種情況，，，，應(yīng)該是標(biāo)程的離散也是這樣把，，，，，， //3 //1 10 //1 3 //6 10 //2 //應(yīng)該是3

總結(jié)

• 暑假時接觸過一次數(shù)據(jù)的離散化，，，但是當(dāng)時只是會用就行，，，最終還是忘記了，，，只知道這樣一個名詞，，，這次花了點(diǎn)時間記憶了一下，，，但是還是沒有仔細(xì)深入的看看，，，因?yàn)橐郧翱吹降碾x散化時用的lower_bound()，，，，而且操作更加的復(fù)雜，，，過一段時間再看看把，，，，

• 看到網(wǎng)上好多人用的線段樹的結(jié)構(gòu)和之前寫的那樣一樣，，，build(),update(),query()，，，但就是理解不了，，，QAQ，，，看了kuangbin的寫法反到理解了，，，雖然基本是照搬過來的，，，，再過幾天要重寫一遍，，，

(end)

轉(zhuǎn)載于:https://www.cnblogs.com/31415926535x/p/9782804.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的poj-2528线段树练习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。