BOJ 13547 | 수열과 쿼리 5

mo's 알고리즘으로 쿼리를 정렬해 푸는 문제이다.
바로 전에 평방 분할로 문제를 풀려고 엄청나게 난리치다가 mo's 배우고 이런거 푸니까 심신이 안정된다.
mo's 알고리즘은 좀 더 많은 연습 문제를 풀어볼 예정이다.

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Query{
	int l, r;
	int idx;
};

int n, m;
vector<int> arr;
vector<Query> q;
int ans[100001];
int cnt[1000001];

const int BUCKET_SIZE = 320;

bool _cmp(Query a, Query b){
	int al = a.l / BUCKET_SIZE;
	int bl = b.l / BUCKET_SIZE;
	
	if (al != bl) return al < bl;
	return a.r < b.r;
}

int main(){
	FASTIO;
	
	cin >> n;
	for (int i = 0; i < n; i++){
		int t; cin >> t;
		arr.push_back(t);
	}
	cin >> m;
	for (int i = 0; i < m; i++){
		int l, r; cin >> l >> r;
		q.push_back({l-1, r-1, i});
	}
	
	sort(q.begin(), q.end(), _cmp);
	
	int lp = 1, rp = 0;
	int sum = 0;
	
	for (int i = 0; i < m; i++){
		int l = q[i].l, r = q[i].r;
		int idx = q[i].idx;
		
		while (l < lp){
			cnt[ arr[--lp] ]++;
			if (cnt[ arr[lp] ] == 1) sum++;
		}
		while (l > lp){
			cnt[arr[lp++]]--;
			if (cnt[arr[lp-1]] == 0) sum--;
		}
		while (rp < r){
			cnt[arr[++rp]]++;
			if (cnt[arr[rp]] == 1) sum++;
		}
		while (rp > r){
			cnt[arr[rp--]]--;
			if (cnt[arr[rp+1]] == 0) sum--;
		}
		
		ans[idx] = sum;
	}
	
	for (int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }
	
}