Luogu1382 楼房 (线段树扫描线)

忘是亡心i 2021-11-17 05:10 302阅读 0赞

各种低级错误.jpg，数组开大就过.jpg  
线段树离散化扫描线

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)
    #define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)
    #define Max(a,b) ((a) > (b) ? (a) : (b))
    #define Min(a,b) ((a) < (b) ? (a) : (b))
    #define Fill(a,b) memset(a, b, sizeof(a))
    #define Swap(a,b) a^=b^=a^=b
    #define ll long long
    
    //#define ON_DEBUG
    
    #ifdef ON_DEBUG
    
    #define D_e_Line printf("\n\n----------\n\n")
    #define D_e(x)  cout << #x << " = " << x << endl
    #define Pause() system("pause")
    
    #else
    
    #define D_e_Line ;
    
    #endif
    
    struct ios{
        template<typename ATP>ios& operator >> (ATP &x){
            x = 0; int f = 1; char c;
            for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;
            while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
            x*= f;
            return *this;
        }
    }io;
    using namespace std;
    #define lson rt << 1, l, mid
    #define rson rt << 1 | 1, mid + 1, r
    
    const int N = 400007;
    
    int t[N << 2];
    // do not need pushup
    inline void Pushdown(int rt){
        t[rt << 1] = Max(t[rt << 1], t[rt]);
        t[rt << 1 | 1] = Max(t[rt << 1 | 1], t[rt]);
    }
    inline void Updata(int rt, int l, int r, int L, int R, int w){
        if(L <= l && r <= R){
            t[rt] = Max(t[rt], w);
            return;
        }
        Pushdown(rt);
        int mid = (l + r) >> 1;
        if(L <= mid) Updata(lson, L, R, w);
        if(R > mid)  Updata(rson, L, R, w);
    }
    inline int Query(int rt, int l, int r, int x){
        if(l == r) return t[rt];
        Pushdown(rt);
        int mid = (l + r) >> 1;
        if(x <= mid) return Query(lson, x);
        else return Query(rson, x);
    }
    
    int x[N], y[N], h[N];
    int a[N << 1];
    int main(){
        int n;
        io >> n;
        R(i,1,n){
            io >> h[i] >> x[i] >> y[i];
            a[(i << 1) - 1] = x[i];
            a[i << 1] = y[i];
        }
        
        sort(a + 1, a + (n << 1) + 1);
        int m = unique(a + 1, a + (n << 1) + 1) - a - 1;
        
        R(i,1,n){
            x[i] = lower_bound(a + 1, a + m + 1, x[i]) - a;
            y[i] = lower_bound(a + 1, a + m + 1, y[i]) - a;
            
            Updata(1, 1, m, x[i], y[i] - 1, h[i]); // how can I miss m as n, how can I ! how can I ! Ahhhhhhhhhhhhhhhhhhh
            
        }
        int tot = 0, last = 0;
        x[++tot] = a[1];
        y[tot] = 0;
        R(i,1,m - 1){
            int H = Query(1, 1, m, i);
            if(H != last){
                x[++tot] = a[i];
                y[tot] = H;
                x[++tot] = a[i + 1];
                y[tot] = H;
            }
            else{
                x[tot] = a[i + 1];
            }
            last = H;
        }
        
        printf("%d\n", tot + 1);
        R(i,1,tot){
            printf("%d %d\n", x[i], y[i]);
        }
        printf("%d 0", a[m]);
        
        return 0;
    }

![1570282-20190720215425206-599658474.png][]

转载于:https://www.cnblogs.com/bingoyes/p/11219466.html

[1570282-20190720215425206-599658474.png]: /images/20211116/2b5a14301e114dfebebbbd03728183aa.png