백준[baekjoon] 8462

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef long long LL;

const int MAX_N = 100010;
int sqrtN;

struct Query {
	int idx, s, e;
	bool operator < (Query &x) {
		if (s / sqrtN != x.s / sqrtN) return s / sqrtN < x.s / sqrtN;
		return e < x.e;
	}
};

vector<Query> query;
int arr[MAX_N], cnt[MAX_N*10];
LL ret = 0, ans[MAX_N];

void add(int x)
{
	ret += (LL)(2 * ++cnt[x] - 1)*x;
	
}

void sub(int x)
{
	ret -= (LL)(2 * --cnt[x] + 1)*x;
}

int main()
{
	ios_base::sync_with_stdio(false);	cin.tie(0);
	int n, q;
	cin >> n; sqrtN = (int)sqrt(n);
	cin >> q;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	
	for (int i = 0; i < q; i++) {
		int s, e; cin >> s >> e;
		query.push_back({ i,s,e });
	}
	sort(query.begin(), query.end());

	int s = 0, e = 0;
	
	for (int i = 0; i < q; i++) {
		while (s < query[i].s) sub(arr[s++]);
		while (s > query[i].s) add(arr[--s]);
		while (e < query[i].e) add(arr[++e]);
		while (e > query[i].e) sub(arr[e--]);
		ans[query[i].idx] = ret;
	}

	for (int i = 0; i < q; i++)
		cout << ans[i] << "\n";
	return 0;
}

모스 알고리즘(MO's algorithm) 공부하다 푼 문제중 인상깊었다.