취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24941번 문제인 줄넘기이다.
문제는 아래 링크를 확인하자.

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

어떤 학생이 줄넘기 줄을 왼쪽에서 잡고 있는다면 이 때 오른쪽에서 줄을 잡고 있을 학생의 위치는 고정되어있다는 점에 주목하자. 즉, 각 학생에 대하여 그 학생이 왼쪽에서 줄을 잡고 줄넘기를 한다면 그 때의 줄넘기에 참여하는 학생의 수는 항상 고정되어있다는 점에 주목하자.

따라서, Q개의 질문에서 주어지는 각 구간을 [L, R]로 표현할 때, 질문들을 R 오름차순으로 정렬해두고 스위핑해나가며 [1, R] 구간 내에서 새로 가능해진 줄넘기의 구간을 업데이트해나가는, 각 학생이 왼쪽에서 줄을 잡고 줄넘기를 할 때의 참여 학생수를 원소로 갖는 RMQ 세그먼트트리로 문제를 해결할 수 있다.

가능한 줄넘기의 구간들은 map을 이용하여 간단히 찾을 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int arr[500001];
int ans[500001];
int seg[1048577];

int upd(int L, int R, int qI, int qVal, int sI) {
	if (R < qI || qI < L) return seg[sI];
	if (L == R) return seg[sI] = qVal;
	return seg[sI] = max(upd(L, (L + R) / 2, qI, qVal, sI * 2), upd((L + R) / 2 + 1, R, qI, qVal, sI * 2 + 1));
}

int qry(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR) return seg[sI];
	return max(qry(L, (L + R) / 2, qL, qR, sI * 2), qry((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

map<int, int> mp;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> upd_PQ; // {오른쪽끝,왼쪽끝}
priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> qry_PQ; // {{오른쪽끝,왼쪽끝},쿼리번호}


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

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (mp.find(x) == mp.end()) mp.insert({ x,i });
		else {
			upd_PQ.push(make_pair(i, mp[x]));
			mp[x] = i;
		}
	}

	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int L, R; cin >> L >> R;
		qry_PQ.push(make_pair(make_pair(R, L), i));
	}

	while (!qry_PQ.empty()) {
		int id_qry = qry_PQ.top().second;
		int L = qry_PQ.top().first.second, R = qry_PQ.top().first.first;
		while (!upd_PQ.empty()) {
			if (upd_PQ.top().first > R) break;
			upd(1, N, upd_PQ.top().second, (upd_PQ.top().first - upd_PQ.top().second + 1), 1);
			upd_PQ.pop();
		}
		ans[id_qry] = qry(1, N, L, R, 1);
		qry_PQ.pop();
	}

	for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}