글 읽기 - 틀왜맞

dohoon 3년 전 0

32번 줄과 33번 줄 사이에

fill_n(tree,4*n,make_pair(INT_MAX,0)); 구문을 넣지 않았는데도 맞는 이유는 뭘까요?

저렇게 항등원으로 초기화가 안 되어있으면 업데이트에서 새로운 원소가 다 먹히게 될 것 같은데... 왜 맞는거죠?

#include <bits/stdc++.h>
#define endl '\n'
#define REP(i,a,b) for (int i = a; i <= b; ++i)
#define PER(i,front,back) for (int i = back; i >= front; --i)
#define all(x) x.begin(), x.end()
#define debug cout << "dbg"
#define debugprint(x) cout << endl << #x << " is " << x << endl
using namespace std; void solve(); int main() {ios::sync_with_stdio(0); cin.tie(0); solve();}
using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;

const int N = 4e5+3;
ii tree[N];

void update(int t, int x, iii node) {
    auto [k,l,r] = node;
    if (t < l || r < t) return;
    if (l == r) {tree[k] = {x,t}; return;}
    int m = (l+r)>>1;
    update(t,x,{k<<1,l,m}); update(t,x,{(k<<1)|1,m+1,r});
    tree[k] = min(tree[k<<1],tree[(k<<1)|1]);
}

auto query(ii range, iii node) {
    auto [s,e] = range; auto [k,l,r] = node;
    if (e < l || r < s) return tree[0];
    if (s <= l && r <= e) return tree[k];
    int m = (l+r)>>1;
    return min(query(range,{k<<1,l,m}),query(range,{(k<<1)|1,m+1,r}));
}

void solve() {
    int n; cin >> n;
    REP(i,1,n) {
        int x; cin >> x;
        update(i,x,{1,1,n});
    }
    int m; cin >> m;
    REP(i,1,m) {
        int command; cin >> command;
        if (command == 1) {
            int i, v; cin >> i >> v;
            update(i,v,{1,1,n});
        } else cout << query({1,n},{1,1,n}).second << endl;
    }
}

wider93 3년 전 1

빈 원소가 하나라도 있으면 그렇게 되는데, 33번 줄 루프가 끝난 시점에서는 n개의 끝 노드가 모두 차있게 되고,

n-1개의 중간 노드들은 어차피 양쪽이 다 차있는 상태에서 한 번씩은 업데이트가 진행된 상태로 남는 것 같네요

dohoon 3년 전 0

아 곰곰히 생각해보니 그렇네요!

33번 줄 루프 내에서 이미 다 업데이트가 되는 것인데, 그 과정이 다음과 같겠군요!

임의의 중간노드는 자식노드 2개의 재귀 호출에 의해서 업데이트 될 수 있는데, 앞 자식 노드에서는 작동하지 않지만, 뒤 자식 노드에 의해 결정적으로 업데이트 되기 때문에 정당해지는 신기한 상황이군요.

그래도 되게 불안정한 상태이니 fill을 쓰거나 build로 역으로 짜나가는 방식을 써야하겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀왜맞

dohoon 3년 전 0

wider93 3년 전 1

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말