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

Baekjoon Online Judge

Baekjoon Online Judge

www.acmicpc.net

리차오 트리 + 오프라인 동적 연결성으로 풀려는데

왜 틀렸는지 도저히 못 찾겠다

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 2e18;

struct Line {
    ll a,b;
    ll get(ll x) {
        return a*x+b;
    }
};

struct Life {
    Line line;
    ll s,e;
};

struct Node {
    ll l,r;
    ll s,e;
    Line line;    
};

struct Li_Chao {
    vector<Node> tree;
    stack<pair<Node,pair<ll,ll>>> s;
    ll cnt;
    void init(ll s,ll e) {
        tree.push_back({-1,-1,s,e,{0,-inf}});
    }
    
    void update(ll node,Line v) {
        s.push({tree[node],{node,cnt}});
        ll s=tree[node].s,e=tree[node].e;
        ll m=s+e>>1;
        Line low=tree[node].line, high=v;
        if(low.get(s)>high.get(s)) swap(low,high);
        if(low.get(e)<=high.get(e)) {
            tree[node].line=high;
            return;
        }
        if(low.get(m)<high.get(m)) {
            tree[node].line=high;
            if(tree[node].r==-1) {
                tree[node].r=tree.size();
                tree.push_back({-1,-1,m+1,e,{0,-inf}});
            }
            update(tree[node].r,low);
        } else {
            tree[node].line=low;
            if(tree[node].l==-1) {
                tree[node].l=tree.size();
                tree.push_back({-1,-1,s,m,{0,-inf}});
            }
            update(tree[node].l,high);
        }
    }
    
    ll query(ll node,ll x) {
        if(node==-1) return -inf;
        ll s=tree[node].s,e=tree[node].e;
        ll m=s+e>>1;
        if(x<=m) return max(tree[node].line.get(x),query(tree[node].l,x));
        else return max(tree[node].line.get(x),query(tree[node].r,x));
    }
    
    void undo() {
        cnt--;
        while(!s.empty()&&s.top().second.second>cnt) {
            tree[s.top().second.first]=s.top().first;
            s.pop();
        }
    }
    
} seg;

vector<vector<Life>> tree(1200001);
vector<vector<ll>> que(1);

void update(ll node,ll start,ll end,Life life) {
    ll s=life.s,e=life.e;
    if(start>=s&&end<=e) {
        tree[node].push_back(life);
        return;
    }
    if(end<s||start>e) return;
    ll mid=start+end>>1;
    update(node*2,start,mid,life);
    update(node*2+1,mid+1,end,life);
}

void divide(ll node,ll start,ll end) {
    seg.cnt++;
    for(auto i:tree[node]) seg.update(0,i.line);
    if(start!=end) {
        ll mid=start+end>>1;
        divide(node*2,start,mid);
        divide(node*2+1,mid+1,end);
    } else if(que[start][0]==3) {
        ll sol=seg.query(0,que[start][1]);
        if(sol<=-2e18) cout<<"EMPTY\n";
        else cout<<sol<<"\n";
    }
    seg.undo();
}

int main() {
    ll Q,t1,t2,t3=0;
    seg.init(-2e12,2e12);
    cin>>Q;
    for(ll i=1;i<=Q;i++) {
        cin>>t1>>t2;
        if(t1==1) {
            cin>>t3;
            que.push_back({t1,t2,t3});
        } else que.push_back({t1,t2});
        if(t1==2) que[t2].push_back(i);
    }
    for(ll i=1;i<=Q;i++) if(que[i][0]==1) {
        if(que[i].size()==3) update(1,1,Q,{{que[i][1],que[i][2]},i,Q});
        else update(1,1,Q,{{que[i][1],que[i][2]},i,que[i][3]-1});
    }
    divide(1,1,Q);
}

반평면 땅따먹기1은 맞은 거 보면 리차오 트리 기본 구현 자체는 틑린게 없는 거 같고 롤백하는 함수랑 오프라인 동적 연결성 용도로 만든 세그먼트 트리만 추가됨

메인 함수는 쿼리를 배열에 저장한 뒤 한 바퀴 순회하면서 삭제되는 정수쌍들은 수명이 언제인지 추가로 표시하게 구현함