이상한 나라의 갈톤보드

백준 24527번: 이상한 나라의 갈톤보드

아이디어

맨 처음 생각한 아이디어는 그냥 레이지 세그로 푸는거였다. 구간 업데이트와 쿼리를 로그 시간에 처리할 수 있기 때문에 무난하게 통과할 수 있다.

누적합 응용으로 imos법이라는게 있다. a부터 b까지 3을 더한다 하면, diff[a] += 3, diff[b+1] -= 3을 한다. 즉, 차이를 기록한다.
이를 통해 아무리 긴 구간에 더해지는 연산도 상수 시간에 처리할 수 있고, 이를 앞에서부터 더하면서 누적합으로 복원하면 된다.

시작지점 번호가 주어지면, 전체 삼각형에서 맨 오른쪽 값을 미리 저장해둔 벡터에서 이분탐색을 하여 몇층인지 구할 수 있다. 몇층인지 구하고 나면 구간의 사이즈도 구할 수 있고, 구간의 사이즈를 알면 도착지점의 left, right를 다 구할 수 있다.

코드

느리게 갱신되는 세그먼트 트리

#include <bits/stdc++.h>

using namespace std;

#define int long long

int H, Q, R;
vector<double> tree(4*100000), lazy(4*100000);

void propagate(int node, int start, int end) {
    if (lazy[node] > 0) {
        tree[node] += (end-start+1)*lazy[node];
        if (start != end) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

void update(int node, int start, int end, int left, int right, double diff) {
    propagate(node, start, end);
    if (end < left || right < start) return;
    if (left <= start && end <= right) {
        tree[node] += (end-start+1)*diff;
        if (start != end) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }

    update(node*2, start, (start+end)/2, left, right, diff);
    update(node*2+1, (start+end)/2+1, end, left, right, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
    return;
}

double query(int node, int start, int end, int left, int right) {
    propagate(node, start, end);
    if (end < left || right < start) return 0;
    if (left <= start && end <= right) {
        return tree[node];
    }
    return query(node*2, start, (start+end)/2, left, right) + query(node*2+1, (start+end)/2+1, end, left, right);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cout << fixed;
    cout.precision(5);

    cin >> H >> Q >> R;

    vector<int> v;
    for (int i = 1; i <= H; i++) {
        v.push_back(i*(i+1)/2);
    }

    while (Q--) {
        int a, b;
        cin >> a >> b;
        int h = lower_bound(v.begin(), v.end(), a) - v.begin() + 1;
        int sz = H-h+2;
        int diff = h*(h+1)/2 - a;
        int r = H - diff + 1;
        int l = r - sz + 1;
        double s = 1.0*b/sz;
        update(1, 1, H+1, l, r, s);
    }


    while (R--) {
        int a, b;
        cin >> a >> b;
        cout << query(1, 1, H+1, a, b) << '\n';
    }

    return 0;
}

imos

#include <bits/stdc++.h>

using namespace std;

#define int long long

int H, Q, R;
double diff[100003], sum[100003];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cout << fixed;
    cout.precision(5);

    cin >> H >> Q >> R;

    vector<int> v;
    for (int i = 1; i <= H; i++) {
        v.push_back(i*(i+1)/2);
    }

    while (Q--) {
        int a, b;
        cin >> a >> b;
        int h = lower_bound(v.begin(), v.end(), a) - v.begin() + 1;
        int sz = H-h+2;
        int d = h*(h+1)/2 - a;
        int r = H - d + 1;
        int l = r - sz + 1;
        double s = 1.0*b/sz;
        diff[l] += s;
        diff[r+1] -= s;
    }

    double total = 0;
    for (int i = 1; i <= H+1; i++) {
        total += diff[i];
        sum[i] = sum[i-1] + total;
    }

    while (R--) {
        int a, b;
        cin >> a >> b;
        cout << sum[b] - sum[a-1] << '\n';
    }

    return 0;
}

여담

대회때는 long long 대신 int를 써서 몇시간동안 삽질하다 맞았다. 좀 바보같았지만 매우 뿌듯했음.
또 imos법을 사용하는 풀이에서 H가 최대 100,000이므로 r+1이 100,002가 될 수 있다. 배열의 크기를 넉넉하게 잡도록 하자.