D. Vika and Segments

segment tree, geometry, two pointers

출처: Codeforces D. Vika and Segments

SOL)

1) 합칠수 있는 선들은 합친다.

 (vertical, horizontal)

2) open은 -1, 수직선은 0, close는 1로 두고 (순서 중요)

  x를 기준으로 정렬한다.

  open일 경우 해당 맵핑된 y좌표를 업데이트 해준다.

  close일 경우 삭제

3) 수직선이 나올 때 해당 구간에 겹치는게 있는지 

  segment tree를 이용하여 찾는다.

[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

const int N = 200010;

int t[N];
int x1[N], y1[N], x2[N], y2[N];
vector<int> ys;
vector<pair<int, pair<int, int> > > vertical, horizontal;
vector<pair<int, pair<int, int> > >events;
map<int, int> mapy;
int n;
ll ans = 0;

void compress(){
    sort(ys.begin(), ys.end());
    int cnt = 2;
    mapy[ys[0]] = cnt++;
    for (int i = 1; i < ys.size(); i++){
        if (ys[i - 1] != ys[i])
            mapy[ys[i]] = cnt++;
    }
}
vector<pair <int, pair<int, int> > > combine(vector<pair <int, pair<int, int> > > vec){
    vector<pair <int, pair<int, int> > > res;
    if (vec.empty()) return res;

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

    int lmost = vec[0].second.first;
    int rmost = vec[0].second.second;

    for (int i = 1; i < vec.size(); i++){
        if (vec[i - 1].first != vec[i].first || rmost < vec[i].second.first){//안겹침
            res.push_back(mp(vec[i - 1].first, mp(lmost, rmost)));
            lmost = vec[i].second.first;
            rmost = vec[i].second.second;
        }
        else{
            rmost = max(rmost, vec[i].second.second);
        }
    }
    res.push_back(mp(vec[vec.size() - 1].first, mp(lmost, rmost)));
    return res;
}

void update(int i, int v){
    while (i <= mapy.size() + 2){
        t[i] += v;
        i += (i & -i);
    }
}
int sum(int i){
    int res = 0;
    while (i > 0){
        res += t[i];
        i -= (i & -i);
    }
    return res;
}
int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    for (int i = 0; i < n; i++){
        scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
        if (x1[i] > x2[i]) swap(x1[i], x2[i]);
        if (y1[i] > y2[i]) swap(y1[i], y2[i]);
        if (x1[i] == x2[i]) vertical.push_back(mp(x1[i], mp(y1[i], y2[i])));
        else  horizontal.push_back(mp(y1[i], mp(x1[i], x2[i])));
        ys.push_back(y1[i]);
        ys.push_back(y2[i]);
    }

    compress();

    vertical = combine(vertical);
    horizontal = combine(horizontal);

    for (int i = 0; i < vertical.size(); i++){
        ans += vertical[i].second.second - vertical[i].second.first + 1;
        events.push_back(mp(vertical[i].first, mp(0, i)));
    }

    for (int i = 0; i < horizontal.size(); i++){
        ans += horizontal[i].second.second - horizontal[i].second.first&nnbsp;+ 1;
        events.push_back(mp(horizontal[i].second.first, mp(-1, mapy[horizontal[i].first])));
        events.push_back(mp(horizontal[i].second.second, mp(1, mapy[horizontal[i].first])));
    }

    //printf("%I64d", ans);

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

    for (int i = 0; i < events.size(); i++){
        int o = events[i].second.first;
        if (o == -1)
            update(events[i].second.second, 1);
        else if (o == 1)
            update(events[i].second.second, -1);
        else{
            int idx = events[i].second.second;
            ans -= (sum(mapy[vertical[idx].second.second]) - sum(mapy[vertical[idx].second.first] - 1));
        }
    }

    printf("%I64d", ans);

    return 0;
}