[leetcode weekly contest]391. Perfect Rectangle

Problem
   Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Code

const int MAXN = 110000;
int sum[MAXN * 4 + 110];
int cover[MAXN * 4 + 110];
int x[MAXN];
struct Seg {
    int l,r,h;
    int flag;
    Seg() {}
    Seg(int a,int b,int c,int d) {
        l = a;
        r = b;
        h = c;
        flag = d;
    }
    bool operator< (const Seg &b) const {
  if (h != b.h)
        return h < b.h;
  return flag < b.flag;
    }
}seg[MAXN];

class Solution {
public:
 
    void update(int L,int R,int val,int l,int r,int rt) {
        if (L <= l && r <= R) {
            cover[rt] += val;
            sum[rt] = x[r + 1] - x[l];
            return ;
        }
        int m = (l + r) >> 1;
        if (cover[rt] > 0) {
            cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
            cover[rt] = 0;
            sum[rt << 1] = x[m + 1] - x[l];
            sum[rt << 1 | 1] = x[r + 1] - x[m + 1];
        }
  
  if (L <= m)  {
   update(L,R,val,l,m,rt << 1);
  }
  if (m < R) {
      update(L,R,val,m + 1,r,rt << 1 | 1);
  }
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int m = 0;
        int n = rectangles.size();
        for (int i = 0;i < n;i ++) {
            x[m] = rectangles[i][0];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][1],1);
            m ++;
            x[m] = rectangles[i][2];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][3],-1);
   m ++;
        }
        sort(x,x + m);
        sort(seg,seg + m);
        int tot = 1;
        for (int i = 1;i < m;i ++) {
            if (x[i] != x[i - 1]) {
                x[tot ++ ] = x[i];
            }
        }
        memset(cover,0,sizeof(cover));
        memset(sum,0,sizeof(sum));
        int totarea = 0;
        for (int i = 0;i < m - 1;i ++) {
            int l = lower_bound(x,x + tot,seg[i].l) - x ;
            int r = lower_bound(x,x + tot,seg[i].r) - x - 1;
            if (l <= r) {
                update(l,r,seg[i].flag,0,tot - 1,1);
            }
            totarea += sum[1] * (seg[i + 1].h - seg[i].h);
        }


  int area3 = 0;
  vector<pair<int,int> > vec;
  for (int i = 0;i < n;i ++) {
   vec.push_back(make_pair(rectangles[i][0],rectangles[i][1]));
   vec.push_back(make_pair(rectangles[i][2],rectangles[i][3]));
   area3 += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
  }
  sort(vec.begin(),vec.end());
  int curarea = (vec[n * 2 - 1].first - vec[0].first) * (vec[n * 2 - 1].second - vec[0].second);
  return totarea == curarea && totarea == area3;
    }
};