c언어 12986번 화려한 마을2 12999번 화려한 마을 3 (백준)

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

int n, m, rootN;
int num[200002]={}; //특정 숫자의 개수
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 %d", &n, &m); //n m 입력
	int arr[n+1]; //n개의 요소들을 담을 배열
	rootN = sqrt(n); //n의 제곱근
	for(int i=1; i<=n; i++) {
        scanf("%d", &arr[i]); //요소들을 입력
        arr[i]+=100000; //최솟값이 -100000 이므로 배열에서 사용하려고 +100000 을 해줍니다.
    }
	
	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 알고리즘

 

수열과 쿼리 6과 매우 같습니다.

https://h202.tistory.com/449

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

 

쿼리들을 배열과 shell sort가 아닌 구조체와 quick sort로도 시도해 보았으나 시간초과가 떴습니다.

 

shell sort 보다 quick sort가 더 빠르다고 알고 있었기에 시간초과가 없을 줄 알았으나, 저의 실력으로는 이유를 알 수가 없었습니다 (주어지는 쿼리의 정렬 상태에 따른 걸로 보고 있습니다)