백준13548 수열과 쿼리 6

작성일 | In

문제 링크

  • http://icpc.me/13548

사용 알고리즘

  • Mo’s Algorithm

풀이

1
2
3
cnt[x] = 구간에 존재하는 x의 개수
table[y] = (cnt[x] == y)를 만족하는 y의 개수
res = 모든 cnt[x] 중 최댓값

모스 알고리즘을 돌리면서 위 3개의 변수들을 관리해주면 됩니다.

자세한 구현 방법은 아래 코드에서 Plus와 Minus 함수를 참고하시면 됩니다.

전체 코드

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

typedef long long ll;

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;
	}
};

int n, q;
vector<int> v;
vector<Query> query;
int ans[101010];
int cnt[101010];
int table[101010];
int res;

void Plus(int x){
	if(cnt[x] != 0) table[cnt[x]]--;
	cnt[x]++; table[cnt[x]]++;
	res = max(res, cnt[x]);
}

void Minus(int x){
	table[cnt[x]]--;
	if(cnt[x] == res && !table[cnt[x]]) res--;
	cnt[x]--;
	table[cnt[x]]++;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n+1); sqrtN = sqrt(n);
	for(int i=1; i<=n; i++) cin >> v[i];
	cin >> q;
	for(int i=0; i<q; i++){
		int s, e; cin >> s >> e;
		query.push_back({i, s, e});
	}
	sort(query.begin(), query.end());

	int s = 0, e = 0; res = 0;

	for(int i=0; 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";
}