백준 16975번 수열과 쿼리 21 (C++)

2022년 새해가 밝았다.
난 또 나이를 먹어버렸다.

문제링크

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

설명

기존 세그먼트 트리 문제에서는 구간 합이나 구간 곱 등을 구간에 대한 정보를 빠르게 구하고 변경 사항이 있으면 빠르게 수정하기 위해 세그먼트 트리를 활용하였는데 이 문제는 변경 사항만을 lazy propagation을 통해 수정해주면 되는 문제였다.

또한 새로운 변경사항과 기존에 저장된 변경사항의 충돌을 막기 위해 미리미리 확인해야하는 기존 lazy propagation 문제들

(3문제 밖에 안 풀어 보긴 함ㅋㅋㅋㅋ)

과는 달리 이 문제는 index를 입력받고 index번 째의 수만을 출력하는 문제이기 때문에 값을 구하는 과정에만 lazy propagation을 수행하였다.

맨 처음 코드를 잘 작성했다 생각하고 제출했는데 WA를 받았다.
그 후에 설마하면서 아래 코드를 작성해주고 다시 한 번 내 코드의 전반적인 작동 과정을 둘러봤는데 틀린 거 같지 않아 보여 다시 제출했더니 AC를 받았다.

ios_base::sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);

지금까지는 그저 TLE를 받는다면 한 번 써서 다시 제출해보자라는 생각만 했었는데 이제는 그 이유가 궁금해졌다. 구글링을 통해 궁금증을 해결했다.
그 이유에 대한 건 다른 포스트를 통해 다뤄보겠다.

이 포스트는 수열과 쿼리 21거니까...

코드

#include <iostream>
#include <vector>

using namespace std;
vector<long long> arr;
vector<pair<long long, int>> status(262144);

void lazyprop(int start, int end, int node)
{
	if (status[node].second == 1)
	{
		long long value = status[node].first;
		status[node].first = 0;
		status[node].second = 0;
		if (start == end)
		{
			arr[start] += value;
			return;
		}
		if (start != end)
		{
			status[node * 2].first += value;
			status[node * 2 + 1].first += value;
			status[node * 2].second = 1;
			status[node * 2 + 1].second = 1;
		}
	}
}

long long getvalue(int start, int end, int node, int idx)
{
	if (start > idx || end < idx)
		return 0;

	lazyprop(start, end, node);

	if (start == end)
		return arr[start];

	int mid = (start + end) / 2;

	return getvalue(start, mid, node * 2, idx) + getvalue(mid + 1, end, node * 2 + 1, idx);
}

void updatestatus(int start, int end, int left, int right, int node, long long value)
{
	if (start > right || end < left)
		return;

	if (start >= left && end <= right)
	{
		status[node].first += value;
		status[node].second = 1;
		return;
	}

	int mid = (start + end) / 2;

	updatestatus(start, mid, left, right, node * 2, value);
	updatestatus(mid + 1, end, left, right, node * 2 + 1, value);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, qry, a, b;
	long long num;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		arr.push_back(num);
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> qry;
		if (qry == 1)
		{
			cin >> a >> b >> num;
			updatestatus(0, n - 1, a - 1, b - 1, 1, num);
		}
		else
		{
			cin >> num;
			cout << getvalue(0, n - 1, 1, num - 1) << '\n';
		}
	}
	return 0;
}