백준 소스코드 [C++] 13547 수열과 쿼리 5

www.acmicpc.net/problem/13547

13547번: 수열과 쿼리 5

백준 소스코드 [C++] 13547 수열과 쿼리 5

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
typedef long long ll;
using namespace std;
int n, m,sqrtn;
int arr[100001];
int table[1000001];
struct query {
	int idx, i, j;
};
bool compare(query& x,query& y) {
	if (x.i / sqrtn != y.i / sqrtn) return x.i / sqrtn < y.i / sqrtn;
	return x.j < y.j;
}
vector<query> q;
vector<int>res;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	sqrtn = (int)sqrt(n);
	for (int i = 0;i < n;i++)cin >> arr[i];
	cin >> m;
	q.resize(m);
	res.resize(m);
	int x, y;
	for (int a = 0;a < m;a++) {
		cin >> x >> y;
		q[a] = {a,x-1,y-1};
	}

	sort(q.begin(), q.end(),compare);

	int ans = 0;
	int s = q[0].i, e = q[0].j;
	for (int a = s;a <= e;a++) {
		if (table[arr[a]] == 0) ans++;
		table[arr[a]]++;
	}
	res[q[0].idx] = ans;

	for (int a = 1;a < m;a++) {
		while (q[a].i < s) {
			if (table[arr[--s]] == 0) ans++;
			table[arr[s]]++;
		}
		while (q[a].j > e) {
			if (table[arr[++e]] == 0) ans++;
			table[arr[e]]++;
		}
		while (q[a].i > s) {
			table[arr[s]]--;
			if (table[arr[s++]] == 0) ans--;
		}
		while (q[a].j < e) {
			table[arr[e]]--;
			if (table[arr[e--]] == 0) ans--;
		}
		
		res[q[a].idx] = ans;
	}
	for (int i = 0;i < m;i++) cout << res[i] << '\n';
	return 0;
}