백준 문제풀이
백준[baekjoon] 8462
소심야채
2020. 5. 27. 12:01
#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) 공부하다 푼 문제중 인상깊었다.