Comment

yyhseu: 2025-04-18 18:38:18

这破题sb完了，每告诉你楼的最大的宽度，线段树开多大纯靠猜
注意我的的seg的含义：当前区间上的最小的楼的高度
防止加入的时候被lazy下来
同时在add的时候注意是[nums[i].a,nums[i].b-1]
线段树代码奉上
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
struct buildings{
    int a,b,h;
};
const static int MAX=50000;
int seg[MAX<<2];//本质上seg的实际意义是这个区间上的最小高度，但是我们在单点查询的时候查找的是每一个点的高度，因此你会发现add里面的pushUp没了
int update[MAX<<2];
void lazy(int i,int val){
    if(val>seg[i]){
        seg[i]=val;
        update[i]=val;
    }
}
// void pushUp(int i){
//     seg[i]=max(seg[i<<1],seg[i<<1|1]);
// }
void siftDown(int i){
    if(update[i]){
        lazy(i<<1,update[i]);
        lazy(i<<1|1,update[i]);
        update[i]=0;
    }
}
void add(int jobl,int jobr,int jobv,int l,int r,int i){
    //如果能懒下来
    if(jobl<=l&&jobr>=r){
        lazy(i,jobv);
    }
    else{
        siftDown(i);
        int mid=l+(r-l)/2;
        if(jobl<=mid){
            add(jobl,jobr,jobv,l,mid,i<<1);
        }
        if(jobr>mid){
            add(jobl,jobr,jobv,mid+1,r,i<<1|1);
        }
    }
}
int query(int jobl,int jobr,int l,int r,int i){
    if(jobl<=l&&r<=jobr){
        return seg[i];
    }
    else{
        siftDown(i);
        int mid=l+(r-l)/2;
        int ans=INT_MIN;
        if(jobl<=mid){
            ans=max(query(jobl,jobr,l,mid,i<<1),ans);
        }
        if(jobr>mid){
            ans=max(query(jobl,jobr,mid+1,r,i<<1|1),ans);
        }
        return ans;
    }
}
int main(){
    int n;
    cin>>n;
    vector<buildings> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i].a>>nums[i].b>>nums[i].h;
    }
    int mx=0;
    for(int i=0;i<n;i++){
        mx=max(mx,nums[i].b);
    }
    for(int i=0;i<n;i++){
        add(nums[i].a,nums[i].b-1,nums[i].h,0,mx,1);
    }
    vector<int> height(mx+2);
    for(int i=0;i<=mx;i++){
        height[i]=query(i,i,0,mx,1);
    }
    // if(height[0]!=0){
    //     cout<<"0 "<<height[0]<<endl;
    // }
    if(height[0]!=0){
        cout<<"0 "<<height[0]<<endl;
    }
    for(int i=1;i<=mx+1;i++){
        // cout<<height[i]<<endl;
        if(height[i]!=height[i-1]){
            cout<<i<<" "<<height[i]<<endl;
        }
    }
    return 0;
}
/*
如果当前的线段能拦下来就直接去更新，如果不能就懒信息下发
最后相当于是对于每一个位置进行一次query

8
0 5 11
2 7 6
3 9 13
12 16 7
14 25 3
19 22 18
23 29 13
24 28 4

1 11
3 13
9 0
12 7
16 3
19 18
22 3
23 13
29 0
*/

yyhseu: 2025-04-18 18:04:48

这题也没告诉我楼的宽度有多少啊，我线段树都不知道开多大空间，服了qwq

重生之我竟是菜狗: 2022-09-18 19:53:07

It is so hard