c언어 8462번 배열의 힘 (백준)

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

typedef struct Q { //퀴리를 담을 구조체
	int s, e, i;	
}Q;

int main(void) {
	int n, m, nRoot;
	scanf("%d %d", &n, &m);
	nRoot = sqrt(n); //n의 제곱근
	int arr[n+1]; //요소를 담을 배열
    long long num[1000001]={}; //요소의 개수가 몇개 있는지를 나타내는 배열 (long long int으로 만들어야 곱하는 과정에서 overflow가 발생하지 않는다)
	Q query[m], key;
	for(int i=1; i<=n; i++) scanf("%lld", &arr[i]); //요소들 입력
	for(int i=-1; ++i<m; query[i].i=i) { //쿼리들 입력
		int a, b;
		scanf("%d %d", &a,&b);
		query[i].s = a;
		query[i].e = b;
	}
	
	int i, j, gap = m/2; //shell sort, //Mo.s 알고리즘
	while(1) {
		if(gap%2==0) gap++;
		for(i=gap; i<m; i++) {
			key = query[i];
			int a = key.s/nRoot;
			for(j=i-gap; j>=0; j-=gap) {
				int b = query[j].s/nRoot;
				if(a < b) query[j+gap] = query[j];
				else if(a==b && key.e < query[j].e) query[j+gap] = query[j];
				else break;
			}
			query[j+gap] = key;
		}
		if(gap==1) break;
		gap>>=1;
	}
	
    
	int s = query[0].s, e = query[0].s-1;
	long long tmp = 0, ans[m];
	
    //값은 주어진 범위 내에서 특정한 숫자의 개수의 제곱에 특정한 숫자를 곱하는 것이다.
    //일단 long long 타입의 변수를 0으로 준비해놓은 다음
    //범위가 수정될때마다 (1칸씩) 특정한 숫자에 대한 값을 제거 한 다음, 
    //특정한 숫자의 개수의 변화 (1 증가하거나 1 감소하거나) 이후
    //특정한 숫자의 개수의 제곱에 특정한 숫자를 곱한 값을 더해주면 된다.
	for(i=0; i<m; i++) {
		while(s < query[i].s) {
			tmp -= num[arr[s]]*num[arr[s]]*arr[s];
			--num[arr[s]];
			tmp += num[arr[s]]*num[arr[s]]*arr[s];
			s++;
		}
		while(s > query[i].s) {
			s--;
			tmp -= num[arr[s]]*num[arr[s]]*arr[s];
			++num[arr[s]];
			tmp += num[arr[s]]*num[arr[s]]*arr[s];
		}
		while(e < query[i].e) {
			e++;
			tmp -= num[arr[e]]*num[arr[e]]*arr[e];
			++num[arr[e]];
			tmp += num[arr[e]]*num[arr[e]]*arr[e];
		}
		while(e > query[i].e) {
			tmp -= num[arr[e]]*num[arr[e]]*arr[e];
			--num[arr[e]];
			tmp += num[arr[e]]*num[arr[e]]*arr[e];
			e--;
		} ans[query[i].i] = tmp;
	}
	for(i=0; i<m; i++) printf("%lld\n", ans[i]);
}

 

풀이 : Mo.s 알고리즘

 

문제에서는

일정 구간에서 존재하는 각각의 숫자 * 그 숫자들의 개수 * 그 숫자들의 개수 을 구하라고 하고 있습니다.

이 과정에서 overflow가 발생할 수 있으니 long long으로 만들어 주어야 합니다.

 

일단 다른 Mo.s 알고리즘 처럼 요소들을 입력 받고, 쿼리들을 입력 받은 다음 Mo.s 알고리즘으로 정렬하면 됩니다.

그다음 일정 구간에서 존재하는 각각의 숫자 * 그 숫자들의 개수 * 그 숫자들의 개수을 구해야 하는데, 한 쿼리마다 일단 그 구간에 어떤 어떤 숫자들이 있고를 확인 한 다음 위에서 알려고하는 것을 구하기엔 시간이 많이 걸립니다.

 

그러므로, 구간이 1칸씩 변경될때마다, 기존의 그 어떠한 숫자에 대한, 어떠한 숫자 * 어떠한 숫자들의 개수 * 어떠한 숫자들의 개수 을 뺀 다음, 그 어떠한 숫자의 개수를 변화시킨뒤 (범위가 변경되므로) 다시 어떠한 숫자 * 어떠한 숫자들의 개수 * 어떠한 숫자들의 개수 을 더해주면 됩니다.

 

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

8462번: 배열의 힘