백준14897 서로 다른 수와 쿼리 1

작성일 | In

문제 링크

  • http://icpc.me/14897

사용 알고리즘

  • Mo’s Algorithm

풀이

이 문제는 오프라인으로 처리해도 됩니다.

모스 알고리즘을 이용하면 쉽게 풀 수 있습니다.

1
2
3
4
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

pragma 붙이니까 4~500ms정도 빨라지네요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;

int sqrtN = 2000;

struct Query{
	int idx, s, e;

	bool operator < (Query &x){
		if(s/sqrtN != x.s/sqrtN) return s/sqrtN < x.s/sqrtN;
		return e < x.e;
	}
};

vector<int> v, tmp;
vector<Query> query;
int n, q;
int mp[1010101];
vector<int> ans;
int now = 0;

void sub(int i){
	mp[v[i]]--;
	if(mp[v[i]] == 0) now--;
}

void add(int i){
	if(mp[v[i]] == 0) now++;
	mp[v[i]]++;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n+1);
	for(int i=1; i<=n; i++) cin >> v[i];
	tmp = v;
	sort(tmp.begin()+1, tmp.end());
	tmp.erase(unique(tmp.begin()+1, tmp.end()), tmp.end());
	for(int i=1; i<=n; i++){
		v[i] = lower_bound(tmp.begin(), tmp.end(), v[i]) - tmp.begin();
	}

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

	int s = query[0].s;
	int e = query[0].e;
	int idx = query[0].idx;
	for(int i=s; i<=e; i++) add(i);
	ans[idx] = now;

	for(int i=1; i<q; i++){
		idx = query[i].idx;
		while(s < query[i].s) sub(s++);
		while(s > query[i].s) add(--s);
		while(e < query[i].e) add(++e);
		while(e > query[i].e) sub(e--);
		ans[idx] = now;
	}

	for(auto i : ans) cout << i << "\n";
}