언제나 처음처럼

[문제 링크]

세그먼트 트리라고 불리는 구간 트리를 활용하면 쉽게 풀 수 있는 문제였다.

구간의 최솟값을 저장하는 구간 트리는 알고리즘 문제해결 전략에 나와있는대로 구현하였고 구간의 최댓값을 구하기 위해 배열에 -1을 곱한 뒤 구간 트리를 한개 더 만들었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INTMAX = numeric_limits<int>::max();

void getMinus(int& a)
{
	a *= -1;
}

class RMQ {
	int n;
	vector<int> rangeMin;

	int init(const vector<int>& array, int left, int right, int node)
	{
		if (left == right)
			return rangeMin[node] = array[left];
		int mid = (left + right) / 2;
		int leftMin = init(array, left, mid, node * 2);
		int rightMin = init(array, mid + 1, right, node * 2 + 1);

		return rangeMin[node] = min(leftMin, rightMin);
	}

	int query(int left, int right, int node, int nodeLeft, int nodeRight)
	{
		if (right < nodeLeft || nodeRight < left) return INTMAX;
		if (left <= nodeLeft && nodeRight <= right) return rangeMin[node];

		int mid = (nodeLeft + nodeRight) / 2;
		return min(query(left, right, node * 2, nodeLeft, mid),
			query(left, right, node * 2 + 1, mid + 1, nodeRight));
	}

	int update(int index, int newValue, int node, int nodeLeft, int nodeRight)
	{
		if (index < nodeLeft || nodeRight < index) return rangeMin[node];
		if (nodeLeft == nodeRight) return rangeMin[node] = newValue;

		int mid = (nodeLeft + nodeRight) / 2;
		
		return rangeMin[node] = min(update(index, newValue, node * 2, nodeLeft, mid),
			update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
	}

public:
	RMQ(const vector<int>& array)
	{
		n = array.size();
		rangeMin.resize(n * 4);
		init(array, 0, n - 1, 1);
	}

	int query(int left, int right)
	{
		return query(left, right, 1, 0, n - 1);
	}

	int update(int index, int newValue)
	{
		return update(index, newValue, 1, 0, n - 1);
	}
};

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, Q;
		cin >> N >> Q;

		vector<int> board(N);
		for (int i = 0; i < N; i++)
			cin >> board[i];

		RMQ boardMin(board);

		for_each(board.begin(), board.end(), getMinus);

		RMQ boardMax(board);

		for (int i = 0; i < Q; i++)
		{
			int first, last;
			cin >> first >> last;


			cout << -boardMax.query(first, last) - boardMin.query(first, last) << endl;
		}
	}
}

알고리즘 200일 프로젝트 - 143 day