BOJ 15745 - Snow boots (오프라인 쿼리, 유니온 파인드)

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

 

<문제설명>

최대 1e5개의 음이 아닌 정수 n개가 주어진다. 첫번째와 마지막은 0임이 보장된다.

 

쿼리 s d가 최대 1e5개 주어진다.

배열에서 s를 초과하는 연속하는 부분수열의 최대 길이 < d인 경우 1을, 그 외엔 0을 출력한다.

 

<풀이>

s에 대해 내림차순으로 query를 정렬한다.

 

각 쿼리마다 배열에서 서로 인접하면서 s를 초과하는 값을 갖는 인덱스끼리 merge해준다.

(한 번 처리한 값을 중복해서 처리하지 않도록 한다)

 

그러면 각 쿼리마다 집합들 중 최대 크기가 s를 초과하는 연속하는 부분 수열의 길이가 된다.

 

쿼리마다 O(lgN)에 최대값을 찾고 모든 쿼리에 걸쳐 인덱스에 대해 한번씩만 연산하므로 O(QlgN+N)쯤 될 것 같다.

 

<코드>

int n, b,mx,uf[MAX],sz[MAX],a[MAX],ans[MAX];
map<int, vector<int>> idx;
vector<T> query;
set<int> st;

int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}
void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	uf[u] = v;
	sz[v] += sz[u];
	sz[u] = 1;
	mx = max(mx, sz[v]);
}

int main() {
	FAST; cin >> n >> b;
	fill(sz, sz + MAX, 1);
	memset(uf, -1, sizeof(uf));

	for (int i = 0; i < n; i++) {
		cin >> a[i];
		st.insert(a[i]);
		idx[a[i]].push_back(i);
	}

	for (int i = 0, s, d; i < b; i++) {
		cin >> s >> d;
		query.push_back({ s,d,i });
	}
	sort(query.begin(), query.end(), [](T t1, T t2) {
		return get<0>(t1) > get<0>(t2);
		});

	for (int i = 0, s, d, t; i < b; i++) {
		tie(s, d, t) = query[i];
		while (st.upper_bound(s) != st.end()) {
			mx = max(mx, 1);
			auto it = st.rbegin();
			for (int j : idx[*it]) {
				if (a[j - 1] > s) merge(j, j - 1);
				if (a[j + 1] > s) merge(j, j + 1);
			}
			st.erase(*it);
		}

		ans[t] = (mx < d);
	}

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

 

<생각>

푸는 법을 알아도 구현하기가 쉽지 않은 문제. 어떤 값(인덱스)를 중복해서 처리하지 않도록 오프라인 쿼리를 이용한 것 유념