백준
백준 소스코드 [C++] 1275 커피숍 2
Hani_Levenshtein
2020. 11. 11. 12:00
1275번: 커피숍2
첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합
www.acmicpc.net
백준 소스코드 [C++] 1275 커피숍 2
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
int n, m;
vector<ll> tree,arr;
void input() {
cin >> n >> m ;
arr.resize(n);
tree.resize(4 * n);
for (int i = 0;i < n;i++) cin >> arr[i];
}
ll init(int i,int S,int E) {
if (S == E) return tree[i] = arr[S];
else return tree[i] = init( 2 * i, S, (S + E) / 2)
+ init(2 * i + 1, (S + E) / 2 + 1, E);
}
void update(int i, int S, int E, int idx, ll gap) {
if (idx < S || E < idx) return;
tree[i] += gap;
if (S != E) {
update(2 * i, S, (S + E) / 2, idx, gap);
update(2 * i + 1, (S + E) / 2 + 1, E, idx, gap);
}
}
ll query( int i, int S, int E, int L, int R) {
if (E < L || R < S) return 0;
if (L <= S && E <= R) return tree[i];
return query(2 * i, S, (S + E) / 2, L, R)
+ query(2 * i + 1, (S + E) / 2 + 1, E, L, R);
}
void output() {
int a, b, c,d;
for (int i = 0;i < m;i++) {
cin >> a >> b >> c>>d;
if (a > b) swap(a, b);
cout << query(1, 0, n - 1, a - 1, b - 1) << '\n';
update(1, 0, n - 1, c - 1, d - arr[c - 1]);
arr[c - 1] = d;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
init(1,0,n-1);
output();
return 0;
}