[BOJ 14413 // C++] Poklon

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

 

이번에 볼 문제는 백준 14413번 문제인 Poklon이다.
문제는 아래 링크를 확인하자.

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

14413번: Poklon

주어지는 쿼리를 [L,R]로 표현할 때 쿼리들을 R 오름차순으로 정렬해 각 쿼리의 답을 구하고 원래의 쿼리 순서대로 답을 출력하는 offline query 테크닉을 이용하자.

 

또한, [L,R]의 구간합을 구하면 원 배열에서 구간 내 정확히 두 번 등장하는 수의 개수를 얻을 수 있는 segment tree를 하나 만들어 문제를 해결하자. 이는 수열의 각 수에 대하여 이 수가 앞서 등장한 가장 가까운 위치, 두번째로 가까운 위치, 세번째로 가까운 위치가 어디인지를 저장해 두는 것으로 구현이 가능하다. 자세한 로직은 아래의 코드를 참고하자.

 

위와 같은 풀이와 별개로, sqrt decomposition을 이용하는 것으로도 이 문제를 해결할 수 있다.

 

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

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

int seg[1048677];

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

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);
}

struct query {
	int qidx, L, R, ans;
	query() {};
	query(int qidx, int L, int R) {
		this->qidx = qidx, this->L = L, this->R = R;
	}
};

bool compR(query& q1, query& q2) {
	return q1.R < q2.R;
}

bool compidx(query& q1, query& q2) {
	return q1.qidx < q2.qidx;
}

int N, Q;
int arr[500001];
map<int, int> mp;
int idx = 1;

query qry[500000];
int curidx = 1, curqry = 0;
int previdx[500001], prevprevidx[500001], prevprevprevidx[500001];

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

	cin >> N >> Q;

	for (int i = 1; i <= N; i++) {
		int x; cin >> x;
		if (mp.find(x) == mp.end()) {
			arr[i] = idx;
			mp.insert(make_pair(x, idx));
			idx++;
		}
		else arr[i] = mp[x];
	}
	for (int i = 0; i < Q; i++) {
		int L, R; cin >> L >> R;
		qry[i] = query(i, L, R);
	}
	sort(qry, qry + Q, compR);

	while (curqry < Q) {
		int& L = qry[curqry].L, & R = qry[curqry].R;
		while (curidx <= R) {
			int num = arr[curidx];
			if (previdx[num] == 0) previdx[num] = curidx;
			else if (prevprevidx[num] == 0) {
				upd(1, N, previdx[num], 1, 1);
				prevprevidx[num] = previdx[num];
				previdx[num] = curidx;
			}
			else if (prevprevprevidx[num] == 0) {
				upd(1, N, prevprevidx[num], -2, 1);
				upd(1, N, previdx[num], 1, 1);
				prevprevprevidx[num] = prevprevidx[num];
				prevprevidx[num] = previdx[num];
				previdx[num] = curidx;
			}
			else {
				upd(1, N, prevprevprevidx[num], 1, 1);
				upd(1, N, prevprevidx[num], -2, 1);
				upd(1, N, previdx[num], 1, 1);
				prevprevprevidx[num] = prevprevidx[num];
				prevprevidx[num] = previdx[num];
				previdx[num] = curidx;
			}
			curidx++;
		}

		qry[curqry].ans = rangesum(1, N, L, R, 1);
		curqry++;
	}

	sort(qry, qry + Q, compidx);
	for (int i = 0; i < Q; i++) cout << qry[i].ans << '\n';
}