[IZhO 2012 Day 2] Monkey and Apple-trees(원숭이와 사과 나무)

지문 링크 / 문제 링크

이거 풀면서 lazy propagation를 짜는 방식도 바꿨다. 속도가 2배가량 향상되고, 훨씬 직관적으로 변했다.

풀이

dynamic segment tree + lazy propagation.

UPD - 구조체 내부 포인터도 0으로 같이 초기화하지 않으면 컴파일 환경에 따라 UB가 발생할 수 있다! 무조건 다 초기화시키자. 그리고 인덱스로 음수가 들어갈 수 있는 경우 단순한 (s+e)/2는 예상한 대로 동작하지 않는다. 따라서 이 블로그에 있는 "코드 조각들" 글에 있는 floor 함수를 이용해서 나눗셈을 처리하자.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

struct node {
    int v; bool z;
    int s, e;
    node *l, *r;
    node(int s, int e): v(0), z(0), s(s), e(e), l(0), r(0) {}
    
    void propagate() {
        int m = (s+e)/2;
        if (!l) l = new node(s,m);
        if (!r) r = new node(m+1,e);
        if (z) {
            l->v = m-s+1;
            r->v = e-m;
            l->z = r->z = 1;
            z = 0;
        }
    }
    
    void update(int a, int b) {
        if (a <= s and e <= b) {
            v = e-s+1, z = 1;
            return;
        }
        if (b < s or e < a) return;
        propagate();
        l->update(a,b), r->update(a,b);
        v = (l?l->v:0) + (r?r->v:0);
    }
    
    int query(int a, int b) {
        if (a <= s and e <= b) return v;
        if (b < s or e < a) return 0;
        propagate();
        return (l?l->query(a,b):0) + (r?r->query(a,b):0);
    }
};

int m;

int main() {
    node *ds = new node(1,int(1e9));
    ll c = 0;
    scanf("%d", &m); while (m--)
    {
        int d, x, y;
        scanf("%d %d %d", &d, &x, &y);
        if (d == 1) {
            c = ds->query(x+c,y+c);
            printf("%lld\n", c);
        } else {
            ds->update(x+c,y+c);
        }
    }
}​

디버깅

아무리 봐도 별 문제가 없길래 구조체에 있는 변수들을 죄다 ll에서 int로 바꿨더니 통과하더라.

동적 할당 쓰는 문제들은 메모리 제한을 유심히 봐야겠다는 것을 깨달았다.

 

 

UPD(2023.03.24): 수정한 템플릿이다. 포인터 구현과 인덱스 구현의 속도 차이가 꽤 크다. auto &[v,z,l,r] 구문이 속도에 영향을 미치지 않기 때문에 가독성 등을 위해 사용하면 좋겠다.

template <ll S, ll E, int N>
struct dynamic_segtree {
    struct node { int v; bool z; int l, r; } C[N]{};
    int c = 0;
    void propagate(int k, ll s, ll e) {
        auto &[v,z,l,r] = C[k];
        ll m = (s+e)>>1;
        if (!l) l = ++c;
        if (!r) r = ++c;
        if (z) {
            C[l].v = m-s+1, C[l].z = 1;
            C[r].v = e-m, C[r].z = 1;
            z = 0;
        }
    }
    void update(int a, int b, int k = 0, ll s = S, ll e = E) {
        auto &[v,z,l,r] = C[k];
        if (a <= s and e <= b) { v = e-s+1, z = 1; return; }
        if (b < s or e < a) return;
        propagate(k,s,e);
        ll m = (s+e)>>1;
        update(a,b,l,s,m), update(a,b,r,m+1,e);
        v = (l?C[l].v:0) + (r?C[r].v:0);
    }
    int query(int a, int b, int k = 0, ll s = S, ll e = E) {
        auto &[v,z,l,r] = C[k];
        if (a <= s and e <= b) return v;
        if (b < s or e < a) return 0;
        propagate(k,s,e);
        ll m = (s+e)>>1;
        return (l?query(a,b,l,s,m):0) + (r?query(a,b,r,m+1,e):0);
    }
};