관리 메뉴

너와 나의 스토리

[BOJ] 1275 커피숍2 본문

Algorithm/세그먼트 트리 (Segment Tree)

[BOJ] 1275 커피숍2

노는게제일좋아! 2019. 9. 11. 13:19
반응형

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

 

 

소스 코드:

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#define swap(a,b) {int t = a; a = b; b = t;}

using namespace std;

typedef long long ll;
int n, m;
ll seg[100001 * 4];
vector<pair<int, int>> v;

ll update(int pos, int val, int node, int x, int y)
{
	if (y<pos || x>pos) return seg[node];
	if (x == y) return seg[node] = val;
	int mid = (x + y) >> 1;
	return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(int low, int hi, int node, int x, int y)
{
	if (y<low || x>hi) return 0;
	if (low <= x&& y <= hi) return seg[node];
	int mid = (x + y) >> 1;
	return query(low, hi, node * 2, x, mid) + query(low, hi, node * 2 + 1, mid + 1, y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n>>m;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		update(i, a, 1, 0, n - 1);
	}
	while (m--)
	{
		int q, w, e, r;
		cin >> q >> w >> e >> r;
		if (q > w) swap(q, w);
		cout << query(q - 1, w - 1, 1, 0, n - 1) << '\n';
		update(e - 1, r, 1, 0, n - 1);
	}
	
	return 0;
}

반응형

'Algorithm > 세그먼트 트리 (Segment Tree)' 카테고리의 다른 글

[BOJ] 12837 가계부 (Hard)  (0) 2019.09.11
[BOJ] 1321 군인  (0) 2019.09.10
[BOJ] 2357 최솟값과 최댓값  (0) 2019.09.10
(BOJ) 1849 순열 / 1777 순열복원  (0) 2019.01.19
(BOJ) 5676 음주 코딩  (0) 2019.01.19
Comments