BOJ 12876 - 반평면 땅따먹기 2

문제 링크 : www.acmicpc.net/problem/12876

문제 태그

Offline dynamic Connectivity , Lichao Tree

문제 풀이

보통 반평면 땅따먹기 1은 풀고 올 것이니 이에 대한 풀이는 알고 있다고 가정하려고 한다. 반평면 땅따먹기 1은 그냥 일반적인 cht optimization이 아니라 직선의 기울기의 단조성이 없기 때문에 lichao tree를 써야하는 문제였다. 반평면 땅따먹기 2에서는 이제 선분이 중간에 없어진다. 

선분에 life가 존재하게 되었다 이러한 문제는 offline dynamic connectivity로 풀 수 있다. lichao tree에서 선분이 추가될 때, 노드를 내려가면서 여러개의 노드를 업데이트 하게 된다. 그 과정에서 노드의 번호와, 업데이트 하기전 노드의 상태를 저장하고 있다가, 그 번호의 노드를 저장한 상태로 되돌리는 것으로 undo 과정을 진행하면 된다. 이때 한 번의 선분추가로 인해 변화된 노드들을 묶어서 한번에 저장하고, 한 번의 undo 과정에서 다 같이 변화시켜야 할 것이다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define mp make_pair
ll inf=2e18+7;
 
struct lin{
    ll a,b;
    ll sol(ll x){
        return a*x+b;
    }
};
 
typedef pair<lin,ll> pli;
typedef pair<pli,ll> plii;
 
vector<plii> stac;
ll ccnt;
 
struct node{
    int l,r;
    ll s,e;
    lin line;
};
 
vector<node> tree;
void init(ll s,ll e){
    tree.push_back({-1,-1,s,e,{0,-inf}});    
}
 
void upt(ll nod,lin nl){
    stac.pb({{tree[nod].line,nod},ccnt});
    ll s=tree[nod].s;
    ll e=tree[nod].e;
    ll m=(s+e)/2;
    lin l1=tree[nod].line;
    lin l2=nl;
    if(l1.sol(s)>l2.sol(s)) swap(l1,l2);
    if(l1.sol(e)<=l2.sol(e)){
        tree[nod].line=l2;
        return ;
    }
    if(l1.sol(m)>=l2.sol(m)){
        tree[nod].line=l1;
        if(tree[nod].l==-1){
            tree[nod].l=tree.size();
            init(s,m);
        }
        upt(tree[nod].l,l2);
    }
    else{
        tree[nod].line=l2;
        if(tree[nod].r==-1){
            tree[nod].r=tree.size();
            init(m+1,e);
        }
        upt(tree[nod].r,l1);
    }
}
 
ll qry(ll nod,ll x){
    if(nod==-1) return -inf;
    if(x<=(tree[nod].s+tree[nod].e)/2) 
        return max(tree[nod].line.sol(x),qry(tree[nod].l,x));
    else 
        return max(tree[nod].line.sol(x),qry(tree[nod].r,x));
}
 
void undo(){
    ll sz=stac.size();
    ccnt--;
    while(sz&&stac[sz-1].ss>ccnt){
        auto k=stac[sz-1];
        tree[k.ff.ss].line=k.ff.ff;
        stac.pop_back();
        sz--;
    }
}
 
ll ans[302020];
 
struct qnode{
    vector<lin> eds;
    ll sol,p1; 
};
qnode qtree[1210101];
 
void uptl(lin ed,ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return;
    if(l<=s&&e<=r){
        qtree[nod].eds.pb(ed);
        return;
    }
    uptl(ed,l,r,s,(s+e)/2,nod*2);
    uptl(ed,l,r,(s+e)/2+1,e,nod*2+1);
}
 
void chk(ll idx,ll pp1,ll s,ll e,ll nod){
    if(idx<s||idx>e) return ;
    if(s==e){
        qtree[nod].sol=1;
        qtree[nod].p1=pp1;
        return ;
    }
    chk(idx,pp1,s,(s+e)/2,nod*2);
    chk(idx,pp1,(s+e)/2+1,e,nod*2+1);
}
 
void dfs(ll s,ll e,ll nod){
    ll sz=qtree[nod].eds.size();
    for(ll i=sz-1;i>=0;i--){
        ccnt++;
        auto k=qtree[nod].eds[i];
        upt(0,k);
    }
    if(s==e){
        if(qtree[nod].sol)
            ans[s]=qry(0,qtree[nod].p1);
        for(auto k:qtree[nod].eds)
            undo();
        return ;
    }
 
    dfs(s,(s+e)/2,nod*2);
    dfs((s+e)/2+1,e,nod*2+1);
    for(auto k:qtree[nod].eds)
        undo();
    
    return ;
}
vector<pli> v;
ll ch[303031];
int main(){
    ll i,j,k,l,m,n,a,b,c;
    scanf("%lld",&n);
    init(-1e9-7,1e9+7);
    v.resize(n+2);
    for(i=1;i<=n;i++){
        v[i].ss=n;
        scanf("%lld",&a);
        if(a==1){
            scanf("%lld %lld",&b,&c);
            v[i].ff.a=b;
            v[i].ff.b=c;
            ch[i]=1;
        }
        else if(a==2){
            scanf("%lld",&b);
            v[b].ss=i;
        }
        else{
            scanf("%lld",&b);
            ch[i]=3;
            chk(i,b,1,n,1);
        }
    }
    for(i=1;i<=n;i++)
        if(ch[i]==1)
            uptl(v[i].ff,i,v[i].ss,1,n,1);
    
    dfs(1,n,1);
    for(i=1;i<=n;i++)
        if(ch[i]==3){
            if(ans[i]<=-1e18-5e17) printf("EMPTY\n");
            else printf("%lld\n",ans[i]);
        }
}