취미로 코딩하기

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

이번에 볼 문제는 백준 14701번 문제인 셔틀버스이다.
문제는 아래 링크를 확인하자.

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

먼저, 학생이 홀수명 있을 때 가운데 학생이 어느 쪽 창가방향으로 이동하게 될지를 기록하자. 가운데 학생은 자신의 왼쪽 학생이 먼저 내리면 왼쪽으로 이동할 것이고 오른쪽 학생이 먼저 내리면 오른쪽으로 이동할 것이다.

위의 작업을 하면, 어떤 N에 대해서도 N명의 학생들을 "왼쪽으로 움직이는 학생들 구간"과 "오른쪽으로 움직이는 학생들 구간"으로 나눌 수 있다.

구간합 세그먼트트리의 각 리프노드를 i번째 학생이 (한 명) 타고 있음을 나타내는 1 또는 타고 있지 않음을 나타내는 0으로 구성하자.

이제 현재 (왼쪽 또는 오른쪽으로부터 현재 남아있는) k번째 원소가 무엇인지를 각 노드의 양쪽 자식에 담긴 하위 리프 개수(남은 사람수)를 활용해 세그먼트트리를 따라 내려간다면 문제를 해결할 수 있다.

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

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

int seg[524289];
int init(int L, int R, int sI) {
	if (L == R) return seg[sI] = 1;
	return seg[sI] = init(L, (L + R) / 2, sI * 2) + init((L + R) / 2 + 1, R, sI * 2 + 1);
}

void update(int L, int R, int qI) {
	int sI = 1;
	while (L < R) {
		seg[sI]--;
		if (qI <= (L + R) / 2) R = (L + R) / 2, sI = sI * 2;
		else L = (L + R) / 2 + 1, sI = sI * 2 + 1;
	}
	seg[sI]--;
}

int kthquery1(int L, int R, int kth) {
	int sI = 1;
	while (L < R) {
		if (seg[sI * 2] >= kth) R = (L + R) / 2, sI = sI * 2;
		else {
			kth -= seg[sI * 2];
			L = (L + R) / 2 + 1, sI = sI * 2 + 1;
		}
	}
	return L;
}

int kthquery2(int L, int R, int kth) {
	int sI = 1;
	while (L < R) {
		if (seg[sI * 2 + 1] >= kth) L = (L + R) / 2 + 1, sI = sI * 2 + 1;
		else {
			kth -= seg[sI * 2 + 1];
			R = (L + R) / 2, sI = sI * 2;
		}
	}
	return L;
}

int rangesum(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 rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

vector<pair<int, int>> query;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int N, Q; cin >> N >> Q;
	int L1 = 1, R1 = N / 2, L2 = N / 2 + 1, R2 = N;
	bool chk = 1;
	while (Q--) {
		int x, y; cin >> x >> y;
		if (chk) {
			if (x == 1) {
				if (y <= N / 2 && (N&1)) L1 = 1, R1 = N / 2 + 1, L2 = N / 2 + 2, R2 = N;
				chk = 0;
			}
		}
		query.push_back(make_pair(x, y));
	}

	init(1, N, 1);

	for (auto p : query) {
		if (p.first == 1) update(1, N, p.second);
		else {
			int q = p.second;
			if (q <= R1) {
				if (rangesum(1, N, L1, R1, 1) < q) cout << 0 << '\n';
				else {
					cout << kthquery1(1, N, q) << '\n';
				}
			}
			else {
				if (rangesum(1, N, L2, R2, 1) < N - q + 1) cout << 0 << '\n';
				else {
					cout << kthquery2(1, N, N - q + 1) << '\n';
				}
			}
		}
	}
}