BOJ 13548 | 수열과 쿼리 6

풀이과정

mo's 알고리즘을 이용해 푸는 문제이다.
cnt[x]가 [i, j] 구간에서의 x의 개수를 의미하도록 하고
table[cnt[x]]가 [i, j] 구간에서의 cnt[x]의 개수를 의미하도록 한다.

이렇게 하면 최대인 cnt[x]가 2개일 때도 충돌 없이 돌아갈 수 있다.

먼저 단순하게 처리한 경우를 보자.

최댓값(max(cnt)를 의미)을 cntmax로 두었는데, 만약 cntmax == cnt[x]인 x가 하나뿐이라면 [i, j]가 달라질 때 새롭게 x가 들어오거나 x가 빠질 때 cnt[x]의 값을 ++하거나 --하는 것으로 처리할 수 있다.

ex) 1 [1 2 3 2 1 1 1 ] 2 1 에서 j가 --되더라도 cntmax는 4 -> 3이 되고, j가 +=2 되더라도 cntmax는 4 -> 5로 단순하게 처리된다.

그러나 cntmax == cnt[x]인 x가 2개 이상이 되면 머리가 복잡해진다.

ex) 1 [1 2 2 1] 3 에서 j--되면 가장 많이 등장하는 1이 하나 줄어 cntmax가 2 -> 1로 처리되지만 사실 가장 많이 등장하는 수는 1뿐만 아니라 2도 있어서
1이 하나 줄더라도 여전히 2가 두 개 있어 cntmax는 2가 되어야 한다.

그래서 table[cnt[x]]를 두어 이런 부분을 처리해준다.

1 [1 2 2 1] 3의 경우에서, table[2]는 2개일 것이다. (cnt[1] == 2, cnt[2] == 2)
만약 j--되어 1 [1 2 2] 1 3이 된다면, 다음 연산을 수행한다.

table[2]--; //이제 cnt[1] != 2이므로
if (cnt[1] == cntmax and table[2] == 0) => cntmax--; //cnt[1]이 가장 큰 값이고, 유일하다면 cntmax를 줄인다.
// mo's 알고리즘에 따라 포인터가 하나씩 움직이므로 cntmax도 하나씩만 움직인다.
cnt[1]--; // 1이 하나 줄었기 때문에
table[cnt[1]]++;

이렇게 table[x] == 0 조건을 통해 방금 줄어든 x의 개수가 '유일한' 최댓값이었는지를 판정해준다.

결론

mo's 알고리즘을 연습하기에 좋은 연습문제인듯 하다.
수열과 쿼리 5를 풀고 도전하기에 좋다.

다만 _Add, _Minus 함수를 만들어내는 과정이 너무 어려웠고, 여러 풀이를 찾아보면서 이해했다.

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Query{
	int l, r;
	int idx;
};

int n, m;
vector<int> arr;
vector<Query> q;
int ans[100001];
int table[100001];
int cnt[100001];

const int BUCKET_SIZE = 320;

bool _cmp(Query a, Query b){
	int al = a.l / BUCKET_SIZE;
	int bl = b.l / BUCKET_SIZE;
	
	if (al != bl) return al < bl;
	return a.r < b.r;
}

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

void _Minus(int x, int &cntmax){
	table[cnt[x]]--;
	if (cnt[x] == cntmax && !table[cnt[x]]) cntmax--;
	cnt[x]--;
	table[cnt[x]]++;
}

int main(){
	FASTIO;
	arr.resize(100001);
	
	cin >> n;
	for (int i = 1; i <= n; i++){
		int t; cin >> t;
		arr[i] = t;
	}
	cin >> m;
	for (int i = 0; i < m; i++){
		int l, r; cin >> l >> r;
		q.push_back({l, r, i});
	}
	
	sort(q.begin(), q.end(), _cmp);
	
	int lp = 0, rp = 0;
	int sum = 0;
	int maxcnt = 0;
	
	for (int i = 0; i < m; i++){
		int l = q[i].l, r = q[i].r;
		int idx = q[i].idx;
		
		
		while (l < lp){
			_Add(arr[--lp], maxcnt);
		}
		while (l > lp){
			_Minus(arr[lp++], maxcnt);
		}
		while (rp < r){
			_Add(arr[++rp], maxcnt);
		}
		while (rp > r){
			_Minus(arr[rp--], maxcnt);
		}
		
		debug << "DEBUG maxcnt :: " << maxcnt << endl;
		
		ans[idx] = maxcnt;
	}
	
	for (int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }
	
}