[백준] 1275: 커피숍2

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

1275번: 커피숍2

백준 2042번: 구간 합 구하기와 유사한 문제이다.

그러나 여기서 중요한 점은 조건의 함정이다.

문제를 보면 $x <= y$라는 점이 전제 되지 않는다.

따라서 만약 $x > y$이면 $swap(x, y)$을 해줘야한다는 점이 이 문제 풀이의 핵심 포인트이다.

 

그리고 까다롭게 입출력에 대한 동기화를 해제하여야만 시간 초과가 되지 않고 통과된다.

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

long long init(vector<long long> &arr, vector<long long> &tree, long long node, long long start, long long end) {
    if(start == end) {
        return tree[node] = arr[start];
    }
    
    long long mid = (start + end) / 2;
    return tree[node] = init(arr, tree, node * 2, start, mid) + init(arr, tree, node * 2 + 1, mid + 1, end);
}

long long sum(vector<long long> &tree, long long node, long long start, long long end, long left, long long right) {
    if(end < left || start > right) return 0;
    if(start >= left && end <= right) return tree[node];
    
    long long mid = (start + end) / 2;
    return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
}

void update(vector<long long> &tree, long long node, long long index, long long diff, long long start, long long end) {
    if(index < start || index > end) return;
    // node로 인덱싱
    tree[node] += diff;
    if(start != end) {
        long long mid = (start + end) / 2;
        update(tree, node * 2, index, diff, start, mid);
        update(tree, node * 2 + 1, index, diff, mid + 1, end);
    }
}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, q, x, y, a, b;
    cin >> n >> q;
    vector<long long> arr(n);
    for(int i = 0;i < n;i++) {
        cin >> arr[i];
    }

    long long depth = (long long) ceil(log2(n));
    long long tree_size = (1 << (depth + 1));
    
    vector<long long> tree(tree_size);
    init(arr, tree, 1, 0, n - 1);

    for(int i = 0;i < q;i++) {
        cin >> x >> y >> a >> b;
        // x > y인 경우도 고려
        if(x > y) swap(x, y);
        cout << sum(tree, 1, 0, n - 1, x - 1, y - 1) << '\n';
        long long diff = b - arr[a - 1];
        arr[a - 1] = b;

        update(tree, 1, a - 1, diff, 0, n - 1);
    }
}