# Share My 60ms C++ Segment Tree Solution

• ``````#define MAXN (10240+5)
#define lson(rt)  (rt << 1)
#define rson(rt)  ((rt << 1) | 1)
#define ls  lson(rt)
#define rs  rson(rt)
#define middle   (left + (right - left)/2)
#define DefaultMinValue  0x7ffffff
#define DefaultMaxValue  0x0000000

struct  SegTreeNode
{
int maxValue, minValue, setValue;
};

int data[MAXN]={0}, nums[MAXN*3];

struct SegTree{
SegTreeNode * segTree;
SegTree(int n){
segTree = new SegTreeNode[n<<4];
}
~SegTree(){ delete [] segTree;}

void buildTree(int rt,int left, int right)/// [left,right]
{
int mid = middle;
if(left == right)
{
segTree[rt].minValue =  segTree[rt].maxValue = data[left];
return;
}
buildTree(lson(rt),left,mid);
buildTree(rson(rt),mid+1,right);
segTree[rt].maxValue = max(segTree[rson(rt)].maxValue,segTree[lson(rt)].maxValue);
segTree[rt].minValue = min(segTree[rson(rt)].minValue,segTree[lson(rt)].minValue);
}
SegTreeNode query(int rt, int left ,int right, const int ql,const int qr)//// min([ql,qr])
{
SegTreeNode tmp;
return segTree[rt];
if(ql <= left && right <= qr)
return segTree[rt];
int mid = middle;
SegTreeNode ans;
if(ql <= mid)
tmp = query(lson(rt), left, mid,ql, qr);
if(mid < qr)
tmp = query(rson(rt), mid+1, right, ql, qr);
ans.minValue = min(ans.minValue,tmp.minValue);
ans.maxValue = max(ans.maxValue,tmp.maxValue);
return ans;
}
void setCurNode(int rt,int left,int right,int value)
{
segTree[rt].setValue = value;
segTree[rt].minValue = value;
segTree[rt].maxValue = value;
}
void pushDown(int rt,int left,int right,int value)
{
if(left != right && value != NotAddValue)
{
setCurNode(ls,left,middle,value);
setCurNode(rs,middle + 1, right,value);
}
}
void setMaintain(int rt,int left,int right)
{
if( right > left ) /// left != right
{
segTree[rt].minValue = min(segTree[lson(rt)].minValue,segTree[rson(rt)].minValue);
segTree[rt].maxValue = max(segTree[lson(rt)].maxValue,segTree[rson(rt)].maxValue);
}
}
void update(int rt,int left, int right,const int cl,const int cr,const int addv)/// set value
{
pushDown(rt,left,right,segTree[rt].setValue);
int mid = middle;
if(cl <= left && right <= cr && addv > segTree[rt].maxValue)
else
{
if(cl <= mid)
if(cr > mid)
}
setMaintain(rt,left,right);
}
};

class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
if(buildings.size() < 1)
return vector<pair<int, int>>();
int cnt = 0;
for (const auto & vec:buildings)
{
nums[cnt++] = vec[0];
nums[cnt++] = vec[1];
nums[cnt++] = vec[1] - 1;
}
sort(nums,nums+cnt);
int ptr = 0;
for(int i =  1; i < cnt; i++)
if(nums[ptr] != nums[i])
nums[++ptr] = nums[i];
cnt = ++ptr;
unordered_map<int,int> mp;
for(int i = 0; i < cnt; i++)
mp[nums[i]] = i+1;
SegTree segtree(cnt);
segtree.buildTree(1,1,cnt);// set zero
for (const auto & vec:buildings)
{
int left = vec[0], right = vec[1] - 1, height = vec[2];
segtree.update(1,1,cnt,mp[left],mp[right],height);
}
vector<pair<int,int>> ret;
for(int i = 1,last = -1; i <= cnt; i++)
{
int tmp = segtree.query(1,1,cnt,i,i).maxValue;
if(tmp != last)
ret.push_back(pair<int,int>(nums[i-1],tmp));
last = tmp;
}
return ret;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.