#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, b;
int arr[303030];
ll cnt[303030], cnt2[303030], reord[303030], ans = 0, res[50505];
const int m = 300000;
struct query{
int idx, lt, rt;
} Q[50505];
bool compare(query p, query q) {
if (p.lt/b == q.lt/b) return p.rt < q.rt;
return (p.lt/b) < (q.lt/b);
}
ll sum[m + 1], xsum[m + 1];
void updatesum(int i, ll x) {
while (i <= m) {
sum[i] += x;
i += (i & -i);
}
}
void updatexsum(int i, ll x) {
while (i <= m) {
xsum[i] += x;
i += (i & -i);
}
}
ll getsum(int i) {
ll ans = 0;
while (i > 0) {
ans += sum[i];
i -= (i & -i);
}
return ans;
}
ll getxsum(int i) {
ll ans = 0;
while (i > 0) {
ans += xsum[i];
i -= (i & -i);
}
return ans;
}
void add(int j) {
int idx, i;
idx = upper_bound(v.begin() + 1, v.begin() + m + 1, cnt[arr[j]]) - v.begin() - 1;
cnt[arr[j]]++;
cnt2[idx]++;
if (idx % 2 == 0) i = m - idx/2 + 1;
else i = (idx + 1) / 2;
reord[i]++;
ans += reord[i];
ans += (i + 1) * getsum(i - 1) - getxsum(i - 1);
ans += (getxsum(m) - getxsum(i)) - (i - 1) * (getsum(m) - getsum(i));
updatesum(i, 1);
updatexsum(i, i);
}
void rem(int j) {
int idx, i;
idx = lower_bound(v.begin() + 1, v.begin() + m + 1, cnt[arr[j]]) - v.begin();
assert(cnt2[idx] == cnt[arr[j]]);
cnt[arr[j]]--;
cnt2[idx]--;
if (idx % 2 == 0) i = m - idx/2 + 1;
else i = (idx + 1) / 2;
reord[i]--;
ans -= reord[i] + 1;
ans -= (i + 1) * getsum(i - 1) - getxsum(i - 1);
ans -= (getxsum(m) - getxsum(i)) - (i - 1) * (getsum(m) - getsum(i));
updatesum(i, -1);
updatexsum(i, -i);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q; b = (int)sqrt(n);
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= q; i++) cin >> Q[i].lt >> Q[i].rt;
for (int i = 1; i <= q; i++) Q[i].idx = i;
sort(Q + 1, Q + q + 1, compare);
int p = 1;
for (int i = 0; i <= n/b; i++) {
if (Q[p].lt/b != i) continue;
for (int i = 1; i <= m; i++) cnt[i] = sum[i] = xsum[i] = 0;
ans = 0;
for (int i = Q[p].lt; i <= Q[p].rt; i++) cnt[arr[i]]++;
for (int i = 1; i <= m; i++) cnt2[i] = cnt[i];
sort(cnt2 + 1, cnt2 + m + 1);
for (int i = 1; i <= m/2; i++) {
reord[i] = cnt2[2 * i - 1];
}
for (int i = 1; i <= m/2; i++) {
reord[m - i + 1] = cnt2[2 * i];
}
for (ll i = 1; i <= m; i++) {
updatesum(i, reord[i]);
updatexsum(i, i * reord[i]);
}
for (ll i = 1; i <= m; i++) ans += reord[i] * (reord[i] + 1) / 2;
for (ll i = 1; i <= m; i++) {
ans += reord[i] * ((i + 1) * getsum(i - 1) - getxsum(i - 1));
}
res[Q[p].idx] = ans;
p++;
while (p <= q && Q[p].lt/b == i) {
for (int j = Q[p - 1].rt + 1; j <= Q[p].rt; j++) add(j);
if (Q[p - 1].lt > Q[p].lt) for (int j = Q[p].lt; j < Q[p - 1].lt; j++) add(j);
else for (int j = Q[p - 1].lt; j < Q[p].lt; j++) rem(j);
res[Q[p].idx] = ans;
p++;
}
}
for (int i = 1; i <= q; i++) cout << res[i] << "\n";
return 0;
}
Compilation message
diversity.cpp: In function 'void add(int)':
diversity.cpp:55:23: error: 'v' was not declared in this scope
55 | idx = upper_bound(v.begin() + 1, v.begin() + m + 1, cnt[arr[j]]) - v.begin() - 1;
| ^
diversity.cpp: In function 'void rem(int)':
diversity.cpp:70:23: error: 'v' was not declared in this scope
70 | idx = lower_bound(v.begin() + 1, v.begin() + m + 1, cnt[arr[j]]) - v.begin();
| ^
