https://www.acmicpc.net/problem/2268
문제
N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i]+A[i+1]+…+A[j]를 구하는 함수이다. (i>j일 경우에는 A[j]+A[j+1]+...+A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.
Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i]=k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.
입력
첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 나타내며, 0일 경우에는 Sum 함수를, 1일 경우에는 Modify 함수를 나타낸다. 다음 두 수는 각 함수의 인자 (i, j)나 (i, k)를 나타낸다. 처음에는 A[1]=A[2]=…A[N]=0이다. Modify인 경우에 1 ≤ k ≤ 100,000 이다.
출력
Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값을 출력한다.
예제 입력 1
3 5
0 1 3
1 1 2
1 2 3
0 2 3
0 1 3
예제 출력 1
0
3
5
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int N, M;
vector <ll> nums;
struct IndexedTree {
vector <ll> tree;
vector <ll> num;
int leafSize = 0, depth = 0;
IndexedTree(vector <ll> num1) {
num = num1;
while (pow(2, depth) < num1.size()) {
depth++;
}
leafSize = pow(2, depth);
tree.resize(2 * leafSize);
}
void update(int node, int left, int right, int index, int diff) {
if (index < left || right < index) {
return;
}
else {
tree[node] += diff;
if (left != right) {
ll mid = (left + right) / 2;
update(node * 2, left, mid, index, diff);
update(node * 2 + 1, mid + 1, right, index, diff);
}
}
}
ll query(int node, int left, int right, int qLeft, int qRight) {
if (right < qLeft || qRight < left) {
return 0;
}
else if (qLeft <= left && right <= qRight) {
return tree[node];
}
else {
ll mid = (left + right) / 2;
return query(node * 2, left, mid, qLeft, qRight) + query(node * 2 + 1, mid + 1, right, qLeft, qRight);
}
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("input.txt", "r", stdin);
cin >> N >> M;
nums.resize(N + 1);
IndexedTree h(nums);
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
int temp = nums[b];
int update = c - temp;
nums[b] = c;
h.update(1, 1, h.leafSize, b, update);
}
else if(a==0) {
if (c < b) {
swap(b, c);
}
cout << h.query(1, 1, h.leafSize, b, c) <<"\n";
}
}
return 0;
}
'개발자 > algorithm' 카테고리의 다른 글
2018 카카오 코딩테스트 6번 : 프렌즈 블록 (c++) (0) | 2020.09.01 |
---|---|
백준 1615번 : 교차개수세기 (c++) (0) | 2020.08.29 |
백준 2618번 : 경찰차 (c++) (0) | 2020.08.28 |
백준 18227번 : 성대나라의 물탱크 (c++) (0) | 2020.08.28 |
2019 카카오 코딩테스트 2번 : 실패율 (c++) (0) | 2020.08.25 |