존못코딩

문제 설명

: Description 그대로다. n개의 원소가 있고, [L,R]의 쿼리가 들어올 때마다
부분 배열의 힘을 구하는것이다.

여기서 라 하면 자연수 s의 개수를 뜻하는데, 부분 배열에서 이 모든 자연수 s에 대해** s
를 구하는 문제이다.

일단 당연한 것은 모든 Query에 대해서 다 훑어보는 식으론 절대 못푼다는 것이다. (의 시간 복잡도를 가지기 때문)

여기서 유용한 것이 Sqrt decomposition (평방분할)을 이용하는 것이다. 평방분할이라는 것은 간단하게 N개의 집합을 sqrt(N)개의 집합으로 나누어 값을 다룬다고 생각하면 되는데,이 문제에서는 Query에 이것을 적용하는 Query Sqrt Decomposition을 이용할 것이다.

query에 대해서 분할하는 것을 Mo's Algorithm이라고도 하는 것 같은데 각각의 query [L,R] 에 대해서 L/sqrt(N)으로 정렬을 한다. (같을 경우 R에 대해서 정렬, 다르게 보자면, (L/sqrt(N))*sqrt(N) + R/sqrt(N) 이라는 value로 오름차순 정렬을 한다고 보면 된다.)

물론, 정렬을 하게 되면 query의 순서가 뒤바뀌기 때문에 따로 index를 저장 해주어야 하고,값을 변경하는 query가 존재하는 경우 적용 할 수 없는 것 같다. 
대신, 구간의 특정 수의 개수라던가 하는 특수한 형태의 문제에는 아주 잘 적용되는 것 같다.

결론적으로,  N개의 원소가 존재하고 query [L,R]이 존재할때, L/sqrt(N)과 R 우선순위로 정렬을 하게 된다면

1. N/sqrt(N) = sqrt(N)개의 집합(이제 Block이라고 하겠다)이 형성된다.

2. 하나의 Block 내에서 query [L,R] -> [L',R']의 변화가 있다고 하면, L'-L <= sqrt(N) 이고 R<=R' 이다. (즉, 같은 Block에서의 L/sqrt(N) 값은 동일하다)

3. 동일 Block 내에서의 R의 변화는 최대 N까지이므로, 최종적으로 모든 query에서의 R은 
시간 복잡도 내에 변화한다.

4. 한 Block 내에서의 L의 range는 sqrt(N)이므로 (L/sqrt(N) 에 대해서 정렬을 해서 집합으로 묶어놨으니 당연한 것이다) 최종적으로 모든 query에 대해서 L은 시간 복잡도 내에서 변화한다.

5. 그렇기 때문에 Mo's algorithm은 의 시간 복잡도를 갖는다. (F는 L,R의 변화 할 때마다 값을 처리해주는 함수를 만들었을때, 그 함수의 처리 시간이다.)

그렇기 때문에 구간의 합 구하기, 최대값 구하기 같은 유형의 문제들을 굳이 segment tree나 fenwick tree를 구현하지 않더라도 최초의 [L,R]을 설정해 놓고 정렬된 query를 쭉 훑으면서 [L,R] -> [L',R']로의 query range를 확장, 축소 해나가면 해결이 가능하다.

더 자세한 내용은 링크를 통해 보는 게 좋겠다.

http://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/

문제링크 [8462 : 배열의 힘]

소스 코드

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stdlib.h>;
using namespace std;
#define ll long long
int h;
struct dot {
	int l, r,id;
	bool operator<(const dot&A)const {
		return l / h == A.l / h ? r < A.r : l / h < A.l / h;
	}
}query[100001];
ll res[100001];
int cnt[1000001];
ll move(int t, int val) { cnt[val] += t; return ((ll)2 * (ll)t*(ll)cnt[val] - 1)*(ll)val; }
/*
   long long int moce(int t,int val)
   개수가 변화 할 때마다, 제곱의 값은 0 1 4 9 16 25.... 로 그  차이가 1,3,5,7,9로 발생한다. 
    즉, 개수-1개 값의 변화가 일어나므로, 2*cnt*k (k=1,-1) 라는 함수로 만들어 낼 수 있다. 
*/

int main()
{
	int n, k, l, r;
	scanf("%d %d", &n, &k);
	h = sqrt(n);
	vector <ll>a(n + 1,0);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &query[i].l, &query[i].r);
		query[i].id = i;
	}sort(query, query + k);

	ll sum = 0;
	l = query[0].l, r = query[0].r;
	for (int i = l; i <= r; i++)sum += move(1, a[i]);
	res[query[0].id] = sum;

	for (int i = 1; i < k; i++)
	{
		while (l > query[i].l)sum += move(1, a[--l]);
		while (l < query[i].l)sum += move(-1, a[l++]);
		while (r > query[i].r)sum += move(-1, a[r--]);
		while (r < query[i].r)sum += move(1, a[++r]);
		res[query[i].id] = sum;
	}
	for (int i = 0; i < k; i++)printf("%lld\n", res[i]);
	return 0;
}