boj7627.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define MAXN 200100
 
typedef struct Rectangle{
    int x1, y1, x2, y2;
}Rectangle;
 
typedef pair<int, pair<int, int> > Event;
 
typedef struct Node1{
    int length, Count;
}Node1;
 
Node1 IndexTree1[2*4*MAXN];
int IndexTree2[2*4*MAXN];
int p = 1;
 
void init_IndexTree(const vector<int>& ys){
    int N = ys.size();
    while (N > p) p <<= 1;
    //바닥층 초기화
    for (int i = 0; i < N - 1; i++)
        IndexTree1[i + p].length = ys[i + 1] - ys[i];
    //부모노드 초기화
    for (int i = p - 1; i >= 1; i--)
        IndexTree1[i].length = IndexTree1[i * 2].length + IndexTree1[i * 2 + 1].length;
}
 
 
void update(int left, int right, int delta){
    left += p;
    right += p;
    while (left <= right){
        if (left & 1){
            //처음 추가될 때
            if (IndexTree1[left].Count == 0){
                IndexTree1[left].Count += delta;
                IndexTree2[left] = IndexTree1[left].length;
                for (int i = (left>>1); i >= 1; (i >>= 1)){
                    if (IndexTree1[i].Count >= 1) break;
                    IndexTree2[i] = IndexTree2[i * 2] + IndexTree2[i * 2 + 1];
                }
            }
            else{
                IndexTree1[left].Count += delta;
                if (IndexTree1[left].Count == 0){
                   //삭제될 때
                    if (p <= left)
                    IndexTree2[left] = 0;
                    else
                    IndexTree2[left] = IndexTree2[left * 2] + IndexTree2[left * 2 + 1];
                     
                    for (int i = (left >> 1); i >= 1; (i >>= 1)){
                        if (IndexTree1[i].Count >= 1) break;
                        IndexTree2[i] = IndexTree2[i * 2] + IndexTree2[i * 2 + 1];
                    }
                }
            }
            left++;
        }
        if (!(right & 1)){
            //처음 추가될 때
            if (IndexTree1[right].Count == 0){
                IndexTree1[right].Count += delta;
                IndexTree2[right] = IndexTree1[right].length;
                for (int i = (right >> 1); i >= 1; (i >>= 1)){
                    if (IndexTree1[i].Count >= 1) break;
                    IndexTree2[i] = IndexTree2[i * 2] + IndexTree2[i * 2 + 1];
                }
            }
            else{
                IndexTree1[right].Count += delta;
                if (IndexTree1[right].Count == 0){
                    //삭제될 때
                    if (p <= right)
                        IndexTree2[right] = 0;
                    else
                        IndexTree2[right] = IndexTree2[right * 2] + IndexTree2[right * 2 + 1];
 
                    for (int i = (right >> 1); i >= 1; (i >>= 1)){
                        if (IndexTree1[i].Count >= 1) break;
                        IndexTree2[i] = IndexTree2[i * 2] + IndexTree2[i * 2 + 1];
                    }
                }
            }
            right--;
        }
        left >>= 1, right >>= 1;
    }
}
 
long long AreaUnion(vector<Rectangle> recs){
    if (recs.empty()) return 0;
 
    vector<int> ys;
    vector<Event> xs;
    for (int i = 0; i < recs.size(); i++){
        ys.push_back(recs[i].y1);
        ys.push_back(recs[i].y2);
        xs.push_back(Event(recs[i].x1, make_pair(1, i)));
        xs.push_back(Event(recs[i].x2, make_pair(-1, i)));
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
 
    map<int, int> yindex;
    for (int i = 0; i < ys.size(); i++)
        yindex[ys[i]] = i;
     
    sort(xs.begin(), xs.end());
     
    init_IndexTree(ys);
     
    long long ret = 0;
    for (int i = 0; i < xs.size(); i++){
        int nowx = xs[i].first;
        int delta = xs[i].second.first;
        int recnum = xs[i].second.second;
        int nowy1 = recs[recnum].y1, nowy2 = recs[recnum].y2;
 
        update(yindex[nowy2], yindex[nowy1] - 1, delta);
 
        long long nowLength;
        if (IndexTree1[1].Count >= 1)
              nowLength = IndexTree1[1].length;
        else
              nowLength = IndexTree2[1];
 
        if (i != xs.size()-1)
        ret += nowLength*(xs[i + 1].first - nowx);
    }
 
    return ret;
}
 
int main(){
    int N;
    cin >> N;
    vector<Rectangle> recs(N);
    for (int i = 0; i < N; i++)
        scanf("%d%d%d%d", &recs[i].x1, &recs[i].x2, &recs[i].y2, &recs[i].y1);
 
    cout << AreaUnion(recs) << endl;
    return 0;
}