LeetCode 218. The Skyline Problem(线段树+离散化)

typedef long long int _int;
class Solution {
public:
    int num[500005];
    int height;
    map<_int,int> m;
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {

        vector<vector<int>> ans;
        if(buildings.size()==0)
            return ans;

        memset(num,0,sizeof(num));

        vector<_int> a;
        for(int i=0;i<buildings.size();i++)
        {
            a.push_back(buildings[i][0]);
            a.push_back(buildings[i][1]);
            a.push_back((_int)buildings[i][1]+1);
        }

        sort(a.begin(),a.end());

        int pos=0;
        vector<_int> b;
        for(int i=0;i<a.size();i++)
        {
            if(m[a[i]]==0)
            {
                m[a[i]] = ++pos;
                b.push_back(a[i]);
            }
        }

        int last;
        for(int i=0;i<buildings.size();i++)
        {
            update(1,1,pos+2,m[buildings[i][0]],m[buildings[i][1]],buildings[i][2]);
        }

        _int start=1;
        height = 0;
        int pre = height;

        while(1)
        {
            pre = height;

            start = query(1,1,pos+2,start,height);

            if(start==-1)
            {
                break;
            }

            vector<int> res;
            if(height < pre)
                res.push_back(b[start-1]-1);
            else
                res.push_back(b[start-1]);

            res.push_back(height);

            ans.push_back(res);
        }
        return ans;


    }

    void pushup(int node)
    {
        if(num[node<<1]==num[node<<1|1])
            num[node]=num[node<<1];
        else
            num[node]=-1;
    }

    void pushdown(int node)
    {
        if(num[node]!=-1)
        {
            num[node<<1]=num[node];
            num[node<<1|1]=num[node];
        }
    }


    void update(int node,_int l,_int r,_int start,_int end,int val)
    {
        if(start<=l&&r<=end)
        {
            if(num[node]!=-1)
            {
                if(num[node]<val)
                    num[node]=val;

                return;
            }

        }
        pushdown(node);

        _int mid = (l+r)>>1;
        if(start<=mid)
            update(node<<1,l,mid,start,end,val);
        if(end >mid)
            update(node<<1|1,mid+1,r,start,end,val);

        pushup(node);
    }

    int query(int node,_int l,_int r,_int start,_int val)
    {
        if(num[node]!=-1)
        {
            if(num[node]==val)
                return -1;
            else
            {
                height = num[node];
                return l;
            }
        }
        pushdown(node);

        _int mid = (l+r)>>1;
        int res;
        if(start<=mid)
        {
            res = query(node<<1,l,mid,start,val);
            if(res!=-1)
                return res;
        }

        res = query(node<<1|1,mid+1,r,start,val);

        pushup(node);

        return res;
    }


};