백준8462 배열의 힘

작성일 | In

문제 링크

  • http://icpc.me/8462

문제 출처

  • 2011 POI ONTAK 62번

사용 알고리즘

  • Mo’s Algorithm

풀이

모스 알고리즘을 구현하면 됩니다.

x라는 값을 구간에 추가하는 경우에는 cnt[x] * cnt[x] * x 를 빼고 cnt[x]를 1 증가시킨 뒤, cnt[x] * cnt[x] * x 를 다시 더해주면 됩니다.
구간에서 제거하는 경우도 비슷하게 처리할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

int sqrtN;

struct Query{
	int idx, s, e;

	bool operator < (Query &rhs){
		if(s/sqrtN != rhs.s/sqrtN) return s/sqrtN < rhs.s/sqrtN;
		return e < rhs.e;
	}
};

vector<int> v;
vector<Query> query;

long long cnt[1010101];
long long res;
long long ans[101010];

int main(){
	int n, q; cin >> n >> q; v.resize(n);
	for(int i=0; i<n; i++) cin >> v[i];
	sqrtN = sqrt(n);

	for(int i=0; i<q; i++){
		int s, e; cin >> s >> e; s--; e--;
		query.push_back({i, s, e});
	}
	sort(query.begin(), query.end());

	int s = query[0].s, e = query[0].e;
	for(int i=s; i<=e; i++){
		res -= cnt[v[i]] * cnt[v[i]] * v[i];
		cnt[v[i]]++;
		res += cnt[v[i]] * cnt[v[i]] * v[i];
	}
	ans[query[0].idx] = res;

	for(int i=1; i<q; i++){
		while(s < query[i].s){
			res -= cnt[v[s]] * cnt[v[s]] * v[s];
			cnt[v[s]]--;
			res += cnt[v[s]] * cnt[v[s]] * v[s];
			s++;
		}
		while(s > query[i].s){
			s--;
			res -= cnt[v[s]] * cnt[v[s]] * v[s];
			cnt[v[s]]++;
			res += cnt[v[s]] * cnt[v[s]] * v[s];
		}
		while(e < query[i].e){
			e++;
			res -= cnt[v[e]] * cnt[v[e]] * v[e];
			cnt[v[e]]++;
			res += cnt[v[e]] * cnt[v[e]] * v[e];
		}
		while(e > query[i].e){
			res -= cnt[v[e]] * cnt[v[e]] * v[e];
			cnt[v[e]]--;
			res += cnt[v[e]] * cnt[v[e]] * v[e];
			e--;
		}
		ans[query[i].idx] = res;
	}
	for(int i=0; i<q; i++) cout << ans[i] << "\n";
}