UVALive - 4108 SKYLINE[线段树]

2022-11-06 09:00:34

Time Limit: 3000MS

64bit IO Format: %lld & %llu

Submit Status UVALive - 4108 SKYLINE[线段树] uDebug

Description

The skyline of Singapore as viewed from the Marina Promenade (shown on the left) is one of the iconic scenes of Singapore. Country X would also like to create an iconic skyline, and it has put up a call for proposals. Each submitted proposal is a description of a proposed skyline and one of the metrics that country X will use to evaluate a proposed skyline is the amount of overlap in the proposed sky-line.

<tex2html_verbatim_mark>

As the assistant to the chair of the skyline evaluation committee, you have been tasked with determining the amount of overlap in each proposal. Each proposal is a sequence of buildings, UVALive - 4108 SKYLINE[线段树] b₁, b₂,..., b_n <tex2html_verbatim_mark>, where a building is specified by its left and right endpoint and its height. The buildings are specified in back to front order, in other words a building which appears later in the sequence appears in front of a building which appears earlier in the sequence.

The skyline formed by the first k <tex2html_verbatim_mark>buildings is the union of the rectangles of the first k <tex2html_verbatim_mark>buildings (see Figure 4). The overlap of a building, b_i <tex2html_verbatim_mark>, is defined as the total horizontal length of the parts of b_i <tex2html_verbatim_mark>, whose height is greater than or equal to the skyline behind it. This is equivalent to the total horizontal length of parts of the skyline behind b_i<tex2html_verbatim_mark>which has a height that is less than or equal to h_i <tex2html_verbatim_mark>, where h_i <tex2html_verbatim_mark>is the height of building b_i <tex2html_verbatim_mark>. You may assume that initially the skyline has height zero everywhere.

Input

The input consists of a line containing the number c <tex2html_verbatim_mark>of datasets, followed by c <tex2html_verbatim_mark>datasets, followed by a line containing the number ` 0'.

The first line of each dataset consists of a single positive integer, n <tex2html_verbatim_mark>(0 < n < 100000) <tex2html_verbatim_mark>, which is the number of buildings in the proposal. The following n<tex2html_verbatim_mark>lines of each dataset each contains a description of a single building. The i <tex2html_verbatim_mark>-th line is a description of building b_i <tex2html_verbatim_mark>. Each building b_i <tex2html_verbatim_mark>is described by three positive integers, separated by spaces, namely, l_i <tex2html_verbatim_mark>, r_i <tex2html_verbatim_mark>and h_i <tex2html_verbatim_mark>, where l_i <tex2html_verbatim_mark>and r_j <tex2html_verbatim_mark>(0 < l_i < r_i UVALive - 4108 SKYLINE[线段树] 100000) <tex2html_verbatim_mark>represents the left and right end point of the building and h_i represents the height of the building.

<tex2html_verbatim_mark>

Output

The output consists of one line for each dataset. The c <tex2html_verbatim_mark>-th line contains one single integer, representing the amount of overlap in the proposal for dataset c<tex2html_verbatim_mark>. You may assume that the amount of overlap for each dataset is at most 2000000.

Note: In this test case, the overlap of building b₁ <tex2html_verbatim_mark>, b₂ <tex2html_verbatim_mark>and b₃ <tex2html_verbatim_mark>are 6, 4 and 4 respectively. Figure 4 shows how to compute the overlap of building b₃ <tex2html_verbatim_mark>. The grey area represents the skyline formed by b₁ <tex2html_verbatim_mark>and b₂ <tex2html_verbatim_mark>and the black rectangle represents b₃ <tex2html_verbatim_mark>. As shown in the figure, the length of the skyline covered by b₃ <tex2html_verbatim_mark>is from position 3 to position 5 and from position 11 to position 13, therefore the overlap of b₃ <tex2html_verbatim_mark>is 4.

Sample Input

Sample Output

题意：在线区间[l,r]查询h是最大值的长度，并更新

很明显区间max

但怎么找这个长度overlap呢？

如果当前区间满足ql<=l&&r<=qr&&h>=t[o].mx 那么就可以被完全覆盖

用lazy维护区间完全覆盖中的最大值，h<t[o].lazy时就不用继续找了(因为h不可能覆盖这个区间了)，有点像个剪枝

否则必须继续找，下传lazy(无需清空自己的标记,剪枝嘛)，合并mx

lazy和mx还有点小细节，比如paint没有用lazy更新mx，其实这不影响，因为先if(h<t[o].lazy) return;了

注意点是区间[i,i+1]

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define m (l+r)/2

#define lson o<<1,l,m

#define rson o<<1|1,m+1,r

#define lc o<<1

#define rc o<<1|1

using namespace std;

typedef long long ll;

const int N=1e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int T,n,ql,qr,h;

struct node{

    int mx,lazy;//totally cover

}t[N<<];

inline void pushDown(int o){

    if(t[o].lazy>t[lc].lazy) t[lc].lazy=t[o].lazy;

    if(t[o].lazy>t[rc].lazy) t[rc].lazy=t[o].lazy;

}

int lap=;

inline void update(int o,int l,int r,int ql,int qr,int h){

    if(h<t[o].lazy) return;

    if(ql<=l&&r<=qr&&h>=t[o].mx){

        t[o].mx=t[o].lazy=h;

        lap+=r-l+;

    }else{

        pushDown(o);

        if(ql<=m) update(lson,ql,qr,h);

        if(m<qr) update(rson,ql,qr,h);

        t[o].mx=max(t[lc].mx,t[rc].mx);

    }

}

int main(){

    T=read();

    while(T--){

        n=read();

        int ans=;

        memset(t,,sizeof(t));

        for(int i=;i<=n;i++){

            ql=read();qr=read()-;h=read();

            lap=;

            update(,,1e5,ql,qr,h);

            //printf("lap %d\n",lap);

            ans+=lap;

        }

        printf("%d\n",ans);

    }

}

码农公寓

相关文章