BOJ 16682 - 삼원색 (D5)

최근에 세그먼트 트리 문제를 많이 푸는데, 그 이유는 nypc 2-A에서 세그먼트 트리에 당했기 때문이다.

사용 알고리즘

Segment Tree + 좌표압축 + 포함배제

 

풀이

앞으로는 Cyan, Magenta, Yellow, Red, Green, Blue, Black을 각각 C, M, Y, R, G, B, K라 부를 것이다.

일단 문제를 봤을 때, 색깔을 고려하지 않으면 떠오르는 문제가 하나 있다.

https://www.acmicpc.net/problem/3392

3392번: 화성 지도

바로 이 문제인데, 직사각형 N개의 합집합 넓이를 O(NlogN)에 구하는 것이다. 약간 다른 점은 이 문제는 좌표압축이 필요하다는 것이고, 위 문제는 필요 없다는 것이다. 근데 저 문제의 좌표압축 버전도 백준에 있다.(...)

https://www.acmicpc.net/problem/7626

7626번: 직사각형

사실 얘를 알고 있었으면, 여기서 포함배제만 적용하면 되는 문제다.

X의 합집합 넓이를 |X|라 하자.

일단, |C|, |M|, |Y|의 넓이는 합집합 영역을 구할 때 각 색깔의 직사각형만 포함시켜서 구해주면 O(NlogN)에 구할 수 있다.

이제 |R|, |G|, |B|를 구할 건데 방법이 같으므로 |R| 기준으로 설명하겠다.

R은 M과 Y의 합성이므로 |M|과 |Y|에서 M, Y 색의 직사각형만 포함시켜서 계산한 합집합을 빼주면 될 것이다. (이를 MY라 하자.)

따라서 |R|은 |M| + |Y| - |MY|이다. 이는 $$  |A\cup  B| = |A| + |B| - |A\cap B|,  |A\cap B| = |A| + |B| - |A\cup  B|$$를 이용한 것이다.

같은 방법으로 |G| = |C| + |Y| - |CY|, |B| = |C| + |M| - |CM|이다.

이제 K만 구하면 된다. R,G,B,C,M,Y를 싹 다 알면 K를 구할 수 있다.

$$  |A\cap B\cap C| = |A\cup B\cup C| - |A| - |B| - |C| + |A\cap B| + |B\cap C| + |C\cap A| $$

에서, $$ |K| = |C\cup M\cup Y| - |C| - |M| - |Y| + |R| + |G| + |B| $$

임을 알 수 있고 전체 합집합은 지금까지 했던것 처럼 O(NlogN)에 구해줄 수 있다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define inf 1e13
ll n;
struct rec{
    ll x,y1,y2,z,color;
    bool operator < (const rec &o) const{
        if(x==o.x){
            if(y1==o.y1){
                if(y2==o.y2){
                    return z<o.z;
                }
                return y2<o.y2;
            }
            return y1<o.y1;
        }
        return x<o.x;
    }
};
vector<ll> p;
struct RECsegtree{
    vector<ll> tree;
    vector<ll> arr;
    RECsegtree(): tree(303030*2,0), arr(303030*2,0) {}
    void upd(ll node, ll s, ll e, ll l, ll r, ll diff){
        if(e<l or r<s)return;
        if(l<=s and e<=r)arr[node] += diff;
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,l,r,diff); upd(node*2+1,mid+1,e,l,r,diff);
        }
        tree[node]=0;
        if(arr[node]>0)tree[node] = p[e]-p[s-1];
        else if(s!=e)tree[node] = tree[node*2]+tree[node*2+1];
    }
    ll get(){
        return tree[1];
    }
} seg;
vector<rec> v;
ll get(vector<rec> &v){
    ll ret = 0;
    ll prvx = -1;
    for(auto [x,y1,y2,z,_] : v){
        if(~prvx)ret += (x-prvx)*seg.get();
        y1 = lower_bound(all(p), y1)-p.begin()+1;
        y2 = lower_bound(all(p), y2)-p.begin()+1;
        prvx=x;
        (z==0 ? seg.upd(1,1,p.size()+1,y1,y2,1) : seg.upd(1,1,p.size()+1,y1,y2,-1));
    }
    return ret;
}
ll C,M,Y,R,G,B,K;	//여기있는 C,M,Y는 무시해도 된다
ll Cp, Mp, Yp, MYp, CYp, CMp;
ll f(bool c, bool m, bool y){
    vector<rec> nv;
    for(auto [x,y1,y2,z,color] : v){
        if(color==0 and !c)continue;
        if(color==1 and !m)continue;
        if(color==2 and !y)continue;
        nv.push_back({x,y1,y2,z,color});
    }
    sort(all(nv));  //혹시몰라서
    return get(nv);
}
int main(){
    fast;
    cin>>n;
    for(int i = 0 ; i < n ; i++){
        ll a,b,c,d; cin>>a>>b>>c>>d;
        char color; cin>>color;
        ll e;
        if(color=='C')e=0;
        if(color=='M')e=1;
        if(color=='Y')e=2;
        a += 1e8; b += 1e8; c+=1e8; d+=1e8;
        a++; b++; c++; d++;
        v.push_back({a,b,d-1,0,e});
        v.push_back({c,b,d-1,1,e});
        p.push_back(b); p.push_back(d-1); p.push_back(d);
    }
    sort(all(p)); comp(p);
    Cp = f(1,0,0), Mp = f(0,1,0), Yp = f(0,0,1), MYp = f(0,1,1), CYp = f(1,0,1), CMp = f(1,1,0);
    R = Yp + Mp - MYp;
    G = Cp + Yp - CYp;
    B = Cp + Mp - CMp;
    K = f(1,1,1)-Cp-Mp-Yp+R+G+B;
    cout<<Cp-G-B+K<<" "<<Mp-R-B+K<<" "<<Yp-G-R+K<<" "<<R-K<<" "<<G-K<<" "<<B-K<<" "<<K;
}