백준 14897 (C++) 서로 다른 수와 쿼리 1

최초 업로드: 2025-11-18 22:00:07

최근 수정 시간: 2025-11-18 22:00:07

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 서로 다른 수와 쿼리 1

[문제 링크](https://www.acmicpc.net/problem/14897)

## 문제 설명

총 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 다음 쿼리를 총 Q번 반복 수행하는 프로그램을 작성하시오. 배열은 1번부터 시작한다.

## 입력

첫째 줄에 배열의 크기 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 배열에 포함된 수가 1번째 수부터 주어진다. 수는 공백으로 구분되어져 있다. 배열에 포함된 수는 1,000,000,000보다 작거나 같은 자연수이다.

셋째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ 1,000,000)가 주어진다. 넷째 줄부터 Q개의 줄에는 쿼리 li, ri가 주어진다. (1 ≤ li ≤ ri ≤ N)

## 출력

첫째 줄부터 Q개의 줄에 쿼리의 답을 한 줄에 하나씩 출력한다.

## 풀이
Mo's + 좌표 압축으로 풀립니다.

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

int a[1'000'001], cur[1'000'001], sqrtN;

struct element {
 int s, e, idx;
 bool operator<(const element el) const {
 if(s/sqrtN!=el.s/sqrtN) return s/sqrtN < el.s/sqrtN;
 return e < el.e;
 }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 sqrtN = sqrt(n);
 vector<int> nums;
 for(int i=1;i<=n;i++) {
 cin >> a[i];
 nums.push_back(a[i]);
 }
 sort(nums.begin(), nums.end());
 nums.erase(unique(nums.begin(), nums.end()), nums.end());
 for(int i=1;i<=n;i++) a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin();

int q; cin >> q;
 vector<element> v(q);
 for(int i=0;i<q;i++) {
 cin >> v[i].s >> v[i].e;
 v[i].idx=i;
 }
 sort(v.begin(), v.end());

cur[0]=1;
 vector<int> res(q);
 int cnt=1, l=0, r=0;
 for(auto [s, e, idx]:v) {
 while(l<s) if(--cur[a[l++]]==0) cnt--;
 while(s<l) if(++cur[a[--l]]==1) cnt++;
 while(r<e) if(++cur[a[++r]]==1) cnt++;
 while(e<r) if(--cur[a[r--]]==0) cnt--;
 res[idx]=cnt;
 }
 for(int e:res) cout << e << '\n';
}
```