백준14413 Poklon

작성일 | In

문제 링크

  • http://icpc.me/14413

문제 출처

  • 2016/2017 COCI Contest #5 5번

사용 알고리즘

  • Mo’s Algorithm

풀이

cnt[x] = x의 개수로 잡고 모스 알고리즘을 돌려주면 됩니다.
단, 수의 범위가 10억 이하이기 때문에 좌표 압축을 해줘야 합니다. lower_bound, unordered_map 등 여러 방법 중 하나를 사용하시면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int sqrtN;

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;
vector<Query> query;
unordered_map<int, int> tmp;
int n, q;
int cnt[505050];
int ans[505050];
int res;

void Plus(int x){
	if(cnt[x]++ == 2) res--;
	else if(cnt[x] == 2) res++;
}

void Minus(int x){
	if(cnt[x]-- == 2) res--;
	else if(cnt[x] == 2) res++;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q; v.resize(n); sqrtN = sqrt(n);

	for(int i=0; i<n; i++){
		cin >> v[i];
		if(tmp.find(v[i]) == tmp.end()){
			int now = tmp.size();
			tmp[v[i]] = now + 1;
		}
	}
	for(int i=0; i<n; i++){
		v[i] = tmp[v[i]];
	}

	for(int i=0; i<q; i++){
		int s, e; cin >> s >> e; s--; e--;
		query.push_back({i, s, e});
	}
	sort(query.begin(), query.end());

	int s = query[0].s, e = query[0].e;
	for(int i=s; i<=e; i++){
		Plus(v[i]);
	} ans[query[0].idx] = res;

	for(int i=1; i<q; i++){
		while(s < query[i].s) Minus(v[s++]);
		while(s > query[i].s) Plus(v[--s]);
		while(e < query[i].e) Plus(v[++e]);
		while(e > query[i].e) Minus(v[e--]);
		ans[query[i].idx] = res;
	}

	for(int i=0; i<q; i++) cout << ans[i] << "\n";
}