[백준OJ] 1275번 커피숍2

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

1275번: 커피숍2

---

 

풀이

세그먼트트리를 이용하여 입력받은 X~Y의 구간합을 구한다음, A번째 숫자를 B로 교환을 Q번 진행한다.

 

세그먼트 트리를 제대로 구현을 했지만, 계속 틀렸습니다가 떠서 문제를 제대로 읽어보니, X>Y인 경우도 입력으로 주어진다는것을 알고, 저 경우 X와 Y를 교환해주었다.

 

그랬더니 정상적으로 돌아가겠지 했는데 시간초과가 떠서 잘 살펴봤는데, 로직상 문제가 없어서 설마하며, C++에서 입출력을 빠르게해주는 다음 코드를 추가시켜줬더니 바로 통과를 했다.

	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 

시간복잡도

세그먼트트리이므로, 업데이트와 합을 구하는 쿼리는 모두 O(logN)이 걸린다. 이 두 쿼리가 Q번 실행되므로, O(QlogN)이 된다.

 

코드

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

class Seg {
public:
	vector<int> arr;
	vector<ll> tree;
	Seg(int n) {
		arr.resize(n);
		int h = (int)ceil(log2(n));
		int tree_size = (1 << (h + 1));
		tree.resize(tree_size);
	}

	void input(int n) {
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
	}

	ll init(int node, int st, int end) {
		if (st == end) {
			return tree[node]=arr[st];
		}

		int middle = (st + end) / 2;
		return tree[node] = init(node * 2, st, middle) + init(node * 2 + 1, middle + 1, end);
	}

	ll query(int node, int st, int end, int l, int r) {
		if (r < st || end < l) {
			return 0;
		}
		if (l <= st && end <= r) {
			return tree[node];
		}

		int middle = (st + end) / 2;
		return  query(node * 2, st, middle, l, r) + query(node * 2 + 1, middle + 1, end, l, r);
	}

	ll update_query(int node, int st, int end, int index,int val) {
		if (index < st || end < index) {
			return tree[node];
		}
		
		if (st == end) {
			return tree[node] = val;
		}
		int middle = (st + end) / 2;
		return tree[node] = update_query(node * 2, st, middle, index, val) + update_query(node * 2+1, middle + 1, end, index, val);
	}
};


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;

	Seg seg(n);
	seg.input(n);
	seg.init(1,0,n-1);
	for (int i = 0; i < q; i++) {
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		if (x > y) {
			int temp = x;
			x = y;
			y = temp;
		}
		cout << seg.query(1,0,n-1,x - 1, y - 1)<<"\n";
		seg.update_query(1,0,n-1, a - 1, b);
	}
	return 0;
}