c언어 13548번 수열과 쿼리 6 (백준)

#include <stdio.h>
#include <math.h>

int n, m, rootN;
int num[100001]={}; //특정 숫자의 개수
int now[100001]={}; //같은 숫자들의 중복의 크기를 담음
//ex 1, 2, 3, 3, 4, 5, 5, 5 now[1] = 3, now[2] = 1, now[3] = 1;

int main(void) {
	scanf("%d", &n); //n 입력
	int arr[n+1]; //n개의 요소들을 담을 배열
	rootN = sqrt(n); //n의 제곱근
	for(int i=1; i<=n; i++) scanf("%d", &arr[i]); //요소들을 입력
	
	scanf("%d", &m); //m 입력
	int query[m][3], ans[m]; //m개의 쿼리들을 담을 배열
	for(int i=-1; ++i<m; query[i][2] = i) scanf("%d %d", &query[i][0], &query[i][1]); //쿼리들을 입력, 또한 query[][2]에 쿼리의 입력된 순서를 저장합니다.
	
    //shell sort을 이용한 mo.s 알고리즘
    //mo.s 알고리즘 (1) start / sqrt 가 더 작은 것은 쿼리가 먼저 처리되도록 
    //(2) start / sqrt 값이 둘 다 같다면, end 값이 더 작은 쿼리가 먼저 처리되도록
	int i, j, key[3], gap = m/2;
	while(1) {
		if(gap%2==0) gap++;
		for(i=gap; i<m; i++) {
			key[0] = query[i][0];
			key[1] = query[i][1];
			key[2] = query[i][2];
			int a = key[0]/rootN; //a는 쿼리의 start에 sqrt을 나눈 값 입니다.
			for(j=i-gap; j>=0; j-=gap) {
				int b = query[j][0]/rootN; //b는 비교하는 쿼리의 start에 sqrt을 나눈 값 입니다.
				if(a < b) { //뒤에 있는 쿼리가 더 start/sqrt값이 작다면 
					query[j+gap][0] = query[j][0];
					query[j+gap][1] = query[j][1];
					query[j+gap][2] = query[j][2];
				} else if(a==b) { //start/sqrt값이 같을 때
					if(key[1] < query[j][1]) { //뒤에 있는 쿼리가 더 end값이 작다면
						query[j+gap][0] = query[j][0];
						query[j+gap][1] = query[j][1];
						query[j+gap][2] = query[j][2];
					} else break;
				} else break;
			}
			query[j+gap][0] = key[0];
			query[j+gap][1] = key[1];
			query[j+gap][2] = key[2];
		}
		if(gap == 1) break;
		gap >>= 1;
	}
	
    //mo.s 알고리즘에 의해 정렬된 쿼리들을 순차적으로 실행
	int s=query[0][0], e=query[0][1], is=0; //s는 start, e는 end, is는 가장 많이 등장하는 수가 몇 번인지를 저장할 변수입니다.
	for(i=s; i<=e; i++) { //첫번째 쿼리에 대한 값 구하기
		int tmp = ++num[arr[i]]; //특정 숫자의 개수 증가
		if(tmp>1) --now[tmp-1]; //예로써, 특정 숫자의 개수가 2개 이상이면, 이전의 now[tmp-1]값을 1감소
		++now[tmp]; //같은 숫자들의 개수에 대응하는 now의 값을 1 증가
		if(tmp > is) is = tmp; //만약 기존의 가장 많이 등장하는 수가 몇 번보다 더 많이 등장하는 수가 생겼다면 그걸로 교체합니다.
	}
	
	ans[query[0][2]] = is; //첫번째 쿼리를 정렬되기 전의 순서에다가 저장합니다.
	
    //두번째 쿼리 이후
	for(i=1; i<m; i++) {
		while(s < query[i][0]) { 
        	//(arr[]) 특정 숫자가 몇개 있는지를 가져 온 다음 이에 대응하는 now의 값을 1 감소합니다.
            //그런다음 이때의 now의 값이 0이면 is(가장 많이 등장하는 수)와 특정 숫자가 몇개 있는지가 같은지를 파악하고
            //이것도 같다면 이제 가장 많이 등장하는 수는 1 감소됩니다. (is--)
			if(--now[num[arr[s]]]<=0 && is == num[arr[s]]) is--;
			--num[arr[s]]; //특정 숫자의 개수도 1 감소
			++now[num[arr[s]]]; //변화된 특정 숫자의 개수에 대한 now을 1 증가
			++s; //s를 1 증가
		}
		while(s > query[i][0]) {
			--s; 
			--now[num[arr[s]]]; //특정 숫자가 몇개 있는지를 가져 온 다음 이에 대응하는 now의 값을 1 감소합니다.
			if(++num[arr[s]] > is) is++; //1 증가한 특정 숫자의 개수가 기존의 is(가장 많이 등장하는 수)보다 크다면 대입해줍니다.
			++now[num[arr[s]]]; //위에서 변화된 특정 숫자가 몇개 있는지를 가져 온 다음 이에 대응하는 now의 값을 1 감소합니다.
		}
        //위의 start을 참고합니다.
		while(e < query[i][1]) {
			++e;
			--now[num[arr[e]]];
			if(++num[arr[e]] > is) is++;
			++now[num[arr[e]]];
		}
		while(e > query[i][1]) {
			if(--now[num[arr[e]]]<=0 && is == num[arr[e]]) is--;
			--num[arr[e]];
			++now[num[arr[e]]];
			--e;
		}
		ans[query[i][2]] = is; //하나의 쿼리를 처리할 때마다, 따로 원래 쿼리의 순서에 맞게 저장해줍니다.
	}
	
	for(int i=0; i<m; i++) printf("%d\n", ans[i]); //처리한 쿼리들의 값을 출력합니다.
	
}

 

 

풀이 : mo.s 알고리즘

 

쿼리들을 빠르게 처리해야 하나, 여기선 처음에 입력받은 값을 수정하는 쿼리가 없기에 segment tree을 사용하지 않습니다.

 

그러나 쿼리들을 입력 받은대로 처리하기엔 시간이 너무 많이 걸리기에 빠르게 처리할 수 있도록 정렬해주어야 하며, 이때 정렬에 사용되는 기법이 mo.s 알고리즘입니다.

 

0. n개의 요소들을 입력받습니다.

1. m개의 쿼리들을 입력받습니다. (입력받은 순서도 따로 저장해 둡니다)

2. 쿼리들을 mo.s알고리즘대로 정렬합니다.

3. 첫번째 쿼리를 해결하고, 값을 원래 쿼리의 순서에 맞게 저장합니다.

4. 두번째 부터 나머지 쿼리들도 해결합니다.

5. 쿼리들의 결과를 원래 입력된 순서대로 출력합니다.

 

https://www.acmicpc.net/problem/13548

13548번: 수열과 쿼리 6