0%

Leetcode699 离散化+线段树

Posted on Edited on

算法题真是几天不写就不行啊……
题面描述 掉落的方块

1000个正方形箱子，位置和边长范围 $10^8$ ，将它们依次像俄罗斯方块一样落下，问每次落下后，屏幕最高的高度是多少。

考虑到要求的答案是整个区间查询，而更新也是区间更新，所以这显然是一个线段树的问题。
每落下一个箱子，就直接将区间值全部更新为箱子所在区间的最大值+箱子高度。

由于箱子很少而距离很远，需要先离散化一下再做。

一个坑点是坐标是1，半径是1的箱子和坐标是2，半径是1的箱子是不会叠起来的。
一个trick是直接将每次查的左端点+1，即[1,1]update的是[2,2]。

一个月没写算法题，很多东西都写不好了。写代码就像背英语，还是要一直坚持的。

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define lson rt<<1
4
#define rson rt<<1|1
5
#define Lson L,mid,lson
6
#define Rson mid+1,R,rson
7
8
class Solution {
9
public:
10
    int value[5040];
11
    int lazy[5040];
12
13
    void build(){
14
        memset(value,0,sizeof(value));
15
        memset(lazy,-1,sizeof(lazy));
16
    }
17
18
    void push_up(int rt){
19
        value[rt]=max(value[lson],value[rson]);
20
    }
21
22
    void push_down(int rt){
23
        if (lazy[rt]!=-1){
24
            lazy[lson]=lazy[rt];
25
            lazy[rson]=lazy[rt];
26
            value[lson]=lazy[rt];
27
            value[rson]=lazy[rt];
28
            lazy[rt]=-1;
29
        }
30
    }
31
32
    void update(int l,int r,int x,int L,int R,int rt){
33
        if (l<=L&&r>=R){
34
            value[rt]=x;
35
            lazy[rt]=x;
36
            return;
37
        }
38
        push_down(rt);
39
        int mid=(L+R)>>1;
40
        if (l<=mid)
41
            update(l,r,x,Lson);
42
        if (r>mid)
43
            update(l,r,x,Rson);
44
        push_up(rt);
45
    }
46
47
    int query(int l,int r,int L,int R,int rt){
48
        if (l<=L&&r>=R){
49
            return value[rt];
50
        }
51
        push_down(rt);
52
        int mid=(L+R)>>1;
53
        int ans=0;
54
        if (l<=mid)
55
            ans=max(ans,query(l,r,Lson));
56
        if (r>mid)
57
            ans=max(ans,query(l,r,Rson));
58
        return ans;
59
    }
60
61
    vector<int> fallingSquares(vector<vector<int>>& positions) {
62
        vector<int> ans;
63
        int rk[2010],n=positions.size(),l,r,x;
64
        for (int i=0;i<n;++i){
65
            rk[2*i]=positions[i][0]+1;
66
            rk[2*i+1]=positions[i][0]+positions[i][1];
67
        }
68
        sort(rk,rk+2*n);
69
        build();
70
        for (int i=0;i<n;++i){
71
            l=lower_bound(rk,rk+2*n,positions[i][0]+1)-rk+1;
72
            r=lower_bound(rk,rk+2*n,positions[i][0]+positions[i][1])-rk+1;
73
            x=query(l,r,1,2*n,1);
74
//            cout<<i<<":"<<endl;
75
//            cout<<"["<<positions[i][0]+1<<" "<<positions[i][0]+positions[i][1]<<"] "<<x<<endl;
76
            update(l,r,x+positions[i][1],1,2*n,1);
77
            ans.push_back(query(1,2*n,1,2*n,1));
78
        }
79
        return ans;
80
    }
81
};