c언어 13028번 민호의 소원 (백준)

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

int main(void)
{
	int n, m, nRoot;
	scanf("%d %d", &n, &m);
	int arr[n+1], num[100001]={}, query[m][3], ans[m];
	nRoot = sqrt(n);
	for(int i=1; i<=n;) scanf("%d", &arr[i++]); //n개의 요소들 입력받음
	for(int i=-1; ++i<m; query[i][2] = i) scanf("%d %d", &query[i][0], &query[i][1]); //m개의 쿼리를 입력받음
	
	int i, j, gap = m/2, key[3]; //Mo.s 알고리즘을 이용한  shell sort
	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]/nRoot;
			for(j=i-gap; j>=0; j-=gap) {
				int b = query[j][0]/nRoot;
				if(a<b || (a==b && key[1] < query[j][1])) {
					query[j+gap][0] = query[j][0];
					query[j+gap][1] = query[j][1];
					query[j+gap][2] = query[j][2];
				} 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;
	}
	
    //쿼리들을 하나씩 처리함
	int s = query[0][0];
	int e = s-1, tmp = 0;
	
	for(int i=0; i<m; i++) {
		while(s<query[i][0]) if(--num[arr[s++]]==2) tmp--;
		while(s>query[i][0]) if(++num[arr[--s]]==3) tmp++;
		while(e<query[i][1]) if(++num[arr[++e]]==3) tmp++;
		while(e>query[i][1]) if(--num[arr[e--]]==2) tmp--;
		ans[query[i][2]] = tmp; //쿼리의 입력순에 맞게 저장
	}
	for(int i=0; i<m; i++) printf("%d\n", ans[i]); //쿼리가 입력된 순서대로 결과를 출력
}

 

풀이 : Mo.s 알고리즘

 

n개의 요소들을 입력 받고, m개의 쿼리들을 입력 받은 뒤

쿼리들을 Mo.s 알고리즘으로 정렬합니다.

 

정렬된 쿼리들을 순서대로 처리하면 됩니다.

 

문제에서는 범위 내 3개이상인 수가 몇개인지를 묻고 있기 때문에,

범위가 증가할때 어떠한 수가 3개이상이 되면 값을 증가 시켜주고

범위가 감소할때 어떠한 수가 3개에서 2개로 감소되면 이 때 값을 감소시켜주면 됩니다.

 

쿼리들의 결과들을 처음 쿼리들을 입력받았던 순서대로 출력하면 됩니다.

 

 

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

13028번: 민호의 소원