BOJ 29335 : Coloring

알고리즘

lazy_segtree, coor_comp ( map )

시간복잡도

$O(QlogQ)$

풀이

문제 조건 상 x좌표가 증가할수록 색칠되어 있는 칸의 수는 감소한다.
따라서 각 쿼리를 $q_x, q_y$라 하면
(색칠되어 있는 칸의 수가 $q_y$ 이상인 가장 작은 x좌표 ~ $q_x$) 구간을
$q_y$로 업데이트 후 전체 합을 구해주면 된다.
이 때 x좌표 범위가 $10^9$까지이므로 좌표압축을 해줘야 한다.

 

구간 update를 진행해야 하므로
{x좌표 두께를 고려한 넓이, max, min}에 대한 lazy seg로 구현하였다.
기존 lazy seg의 update에서 추가적으로
구간 min이 update할 값 이상이면 return,
update 범위 내에 있으며 구간 max가 update할 값 이하면 전체 change,
그 이외의 경우 재귀적으로 진행하였다.

여담

정풀은 map을 사용하는 것 같다. 나중에 시도해보는 걸로...

코드

#include <bits/stdc++.h>  
using namespace std;  
#define ll long long  
#define F first  
#define S second  

pair<ll, ll> a[300005];  
struct tt  
{  
    ll sum, mx, mn;  
}; tt tree[1200005];  
int Q;  
ll lazy[1200005];  
vector<ll> cp;  

void push(int now, int s, int e)  
{  
    if (!lazy[now]) return;  
    tree[now]
    = {lazy[now] * (cp[e] - cp[s-1]), lazy[now], lazy[now]};  
    if (s ^ e) lazy[now<<1] = lazy[now<<1|1] = lazy[now];  
    lazy[now] = 0;  
}  

void update(int now, int s, int e, int l, int r, ll v)  
{  
    push(now, s, e);  
    if (r < s || e < l || tree[now].mn >= v) return;  
    if (l <= s && e <= r && tree[now].mx <= v) {  
        lazy[now] = v;  
        push(now, s, e);  
        return;  
    }    
    int mid = s+e >> 1;  
    update(now<<1, s, mid, l, r, v);
    update(now<<1|1, mid+1, e, l, r, v);  
    tree[now] = {tree[now<<1].sum + tree[now<<1|1].sum,
    max(tree[now<<1].mx, tree[now<<1|1].mx),
    min(tree[now<<1].mn, tree[now<<1|1].mn)};  
}  

ll sum(int now, int s, int e, int l, int r)  
{  
    push(now, s, e);  
    if (r < s || e < l) return 0;  
    if (l <= s && e <= r) return tree[now].sum;  
    int mid = s+e >> 1;  
    return sum(now<<1, s, mid, l, r)
    + sum(now<<1|1, mid+1, e, l, r);  
}  

int main()  
{  
    cin.tie(0)->sync_with_stdio(0);  
    cin>>Q; cp.push_back(0);  
    for (int i = 1; i <= Q; i++) {  
        cin>>a[i].F>>a[i].S; cp.push_back(a[i].F);  
    }    
    sort(cp.begin(), cp.end());  
    for (int i = 1; i <= Q; i++)  
        a[i].F = lower_bound(cp.begin(), cp.end(), a[i].F)
        cp.begin();  
    for (int i = 1; i <= Q; i++) {  
        update(1, 1, Q, 1, a[i].F, a[i].S);  
        cout<<sum(1, 1, Q, 1, Q)<<"\n";  
    } return 0;  
}