2022.06.04 PS 일지

글을 쓰는 시점은 6월 5일 오전 1시이다.

solved.ac 시즌 2가 곧 오전 6시에 시작한다.

첫 시즌 공지 때에는 목표를 2주 정도 동안 Diamond 3로 잡았다.

그런데, 정올을 망친 뒤 슬럼프를 잠깐 가지고 해서 좀 더뎌졌다.

그래서 Diamond 4로 목표를 낮췄는데, 더 우선순위인 일이 생겨 티어를 높이는 것을 중단하였다.

그래서 아쉽게 5시간 남긴 상황에서 D4 - 32로, D4 달성은 무리라 판단하고 이만 자려고 한다.

한 2주 정도 더 레이팅 올리기에 여념을 쏟지 못할 것 같다. 아무튼 시즌 2 기대된다.

 

+) PS 일지도 한동안 OI 문제 풀이에 쏟느라 안 하고 있었는데, 이제는 좀 적을지도?

+) 저번에 Bitaro's Party에 알 수 없는 이유로 cin/cout을 억까 당한 뒤 사흘 이내 정도에 맞먹는 심각한 억까를 당해서 cin/cout을 완전히 은퇴했다. scanf/printf 어서오고~

JuQueen

문제 링크

문제가 요구하는 것만 간략히 설명하면 이렇다:

• 질의: 구간 최대/최소
• 갱신: 구간 증가/감소

후기

레이지 세그트리를 복습 차원에서 좋았다.

구현 방식을 바꾸면서 전보다 레이지에 대한 이해가 더 명료해졌고, 앞으로 언제 짜래도 짤 수 있을 것 같다.

풀이

그냥 하면 된다.

• 노드 자료형을 바깥으로 빼니까 구현의 편의성이 높아지는 것 같다.
• 함수 안에서 선언하니까 터진다. 생성자가 그래서 안 먹는다 ㅠㅠ

#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)

const int C = 5e6+3;
int c, n, o;

struct node {
    int mn, mx;
    void operator += (int y) {
        mn += y, mx += y;
    }
    friend node operator + (node x, node y) {
        return {min(x.mn,y.mn),max(x.mx,y.mx)};
    }
};

template <class A, class B, const int N>
struct lazy_segtree {
    A v[4*N] {0,}; B z[4*N] {0,};
    void propagate(int k, int s, int e) {
        int m = (s+e)/2;
        v[2*k] += z[k], v[2*k+1] += z[k];
        z[2*k] += z[k], z[2*k+1] += z[k];
        z[k] = z[0];
    }
    void update(int a, int b, B &d, int k = 1, int s = 0, int e = N-1) {
        if (a <= s and e <= b) { v[k] += d, z[k] += d; return; }
        if (b < s or e < a) return;
        propagate(k,s,e);
        update(a,b,d,2*k,s,(s+e)/2), update(a,b,d,2*k+1,(s+e)/2+1,e);
        v[k] = v[2*k] + v[2*k+1];
    }
    A query(int a, int b, int k = 1, int s = 0, int e = N-1) {
        if (a <= s and e <= b) return v[k];
        if (b < s or e < a) return v[0];
        propagate(k,s,e);
        return query(a,b,2*k,s,(s+e)/2) + query(a,b,2*k+1,(s+e)/2+1,e);
    }
};

lazy_segtree<node,int,C> ds;

int main() {
    scanf("%d %d %d", &c, &n, &o);
    ds.v[0] = {n,0};
    while (o--) {
        char q[20] {0,};
        scanf("%s", q);
        if (q[0] == 's') {
            int x; scanf("%d", &x);
            printf("%d\n", ds.query(x,x).mn);
        } else {
            int a, b, s;
            if (q[0] == 'g') scanf("%d %d %d", &a, &b, &s);
            else scanf("%d %d", &a, &s), b = a;
            // [a,b] +s
            if (s >= 0) {
                mup(s, n - ds.query(a,b).mx);
                ds.update(a,b,s);
                printf("%d\n", s);
            } else {
                Mup(s, 0 - ds.query(a,b).mn);
                ds.update(a,b,s);
                printf("%d\n", s);
            }
        }
    }
}