[백준]1275_커피숍2(C++)

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

1275번: 커피숍2

문제 풀이만 읽으면 그냥 세그먼트트리 구성하고

(쿼리, update)함수를 쓸줄아냐 모르냐 정도를 묻는 문제인데

정답률이 많이 낮았는데 역시 그럴만한 이유가 있었다.

 

x > y 인경우는 함수에 들어가자마 리턴이 되기 때문에 함수가 돌지 못한다.

#include <iostream>
using namespace std;
#define SWAP(a,b) {int t; t=a; a=b; b=t;}
#define MAX_N 100001

typedef long long ll;
ll tree[MAX_N * 4];

ll update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          return tree[now] = value;
     }
     int mid = (start + end) / 2;
     return tree[now] = update_tree(now * 2, target, start, mid, value) + update_tree(now * 2 + 1, target, mid + 1, end, value);
}

ll query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right) return tree[now];
     int mid = (start + end) / 2;
     return query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end);
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, Q;
     cin >> N >> Q;
     for (int i = 0; i < N; i++) {
          int data; cin >> data;
          update_tree(1, i, 0, N - 1, data);
     }
     for (int i = 0; i < Q; i++) {
          int x, y, a, b;
          cin >> x >> y >> a >> b;
          if (y < x) SWAP(x, y);
          cout << query(1, x - 1, y - 1, 0, N - 1) << "\n";
          update_tree(1, a - 1, 0, N - 1, b);
     }
}