368-B, *1100

Problem - 368B - Codeforces

문제

• 배열 $a = a_{1}a_{2} \cdot \cdot \cdot a_{n},\ (1 \leq n \leq 10^{5})$에 대해
• $a_{l}a_{l+1} \cdot \cdot \cdot a_{n}$ 중 서로 다른 수가 몇 개인지 $m(1 \leq m \leq 10^{5})$번 출력
• $O(nlog\ n)$ 정도의 알고리즘은 통과할 수 있다

 

$O(log\ n!)$

가장 큰 $l$부터 답을 구하여 배열 $arr[l]$에 기록한다
$a_{n}$을 set $s$ 에 삽입한다. 그러면 $O(log\ \mathrm{s.size})$
$$ans[n] = \mathrm{s.size}$$
$a_{n-1}$을 set $s$ 에 삽입한다. 그러면 $O(log\ \mathrm{s.size})$
$$ans[n-1] = \mathrm{s.size}$$

---

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int arr[100001];
int ans[100001];
set<int> s;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    for(int i = n; i >= 1; i--){
        s.insert(arr[i]);
        ans[i] = s.size();
    }
 
    int tmp;
    while(m--){
        cin >> tmp;
        cout << ans[tmp] << endl;
    }
 
    return 0;
}cs