#include <bits/stdc++.h>
using namespace std;
int block;
signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, q;
cin >> n >> q;
const int maxn = 300005, maxq = 50000;
block = sqrt(n) + 3;
int arr[maxn];
for (int i = 0; i < n; i++) cin >> arr[i];
struct query {
pair<int, int> pii;
int in;
bool operator<(query x) const {
if (pii.first / block != x.pii.first / block) return pii < x.pii;
return pii.second > x.pii.second;
}
};
query arrpii[maxn];
for (int i = 0; i < q; i++) {
cin >> arrpii[i].pii.first >> arrpii[i].pii.second;
arrpii[i].pii.first--, arrpii[i].pii.second--;
arrpii[i].in = i;
}
sort(arrpii, arrpii + n);
struct fenwick {
long long arr[2 * maxn + 1] = {};
long long sum(int r) {
int ret = 0;
for (r++; r > 0; r -= r & (-r)) ret += arr[r];
return ret;
}
void add(int in, int val) {
for (in++; in <= 2 * maxn; in += in & (-in)) {
arr[in] += val;
}
}
} ok, rev, normal;
pair<int, int> status[maxn + 1]; // bef, cur
status[0] = {0, n};
for (int i = 1; i <= maxn; i++) status[i] = {n, n};
int at[maxn] = {};
long long curans = 0;
auto add = [&](int in) {
int tmp = status[at[arr[in]]].second - 1;
curans -= long long(at[arr[in]] + 1) * at[arr[in]] / 2;
curans += long long(at[arr[in]] + 2) * (at[arr[in]] + 1) / 2;
int coord;
if (tmp % 2 == 1) {
coord = maxn + 1 + (n - tmp - 1) / 2;
} else if (tmp % 2 == 0) {
coord = maxn - (n - tmp - 1) / 2;
}
normal.add(coord, 1);
ok.add(coord, coord);
rev.add(coord, 2 * maxn - coord);
curans += ok.sum(2 * maxn - 1) - ok.sum(coord) -
(coord - 1) * (normal.sum(2 * maxn - 1) - normal.sum(coord));
curans += rev.sum(coord - 1) - rev.sum(0) -
(2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(0));
status[at[arr[in]]].second--;
at[arr[in]]++;
status[at[arr[in]]].first--;
};
auto rem = [&](int in) {
int tmp = status[at[arr[in]]].first;
curans -= long long(at[arr[in]] + 1) * at[arr[in]] / 2;
curans += long long(at[arr[in]]) * (at[arr[in]] - 1) / 2;
int coord;
if (tmp % 2 == 1) {
coord = maxn + 1 + (n - tmp - 1) / 2;
} else if (tmp % 2 == 0) {
coord = maxn - (n - tmp - 1) / 2;
}
normal.add(coord, -1);
ok.add(coord, -coord);
rev.add(coord, -(2 * maxn - coord));
curans -= ok.sum(2 * maxn - 1) - ok.sum(coord) -
(coord - 1) * (normal.sum(2 * maxn - 1) - normal.sum(coord));
curans -= rev.sum(coord - 1) - rev.sum(0) -
(2 * maxn - coord - 1) * (normal.sum(coord - 1) - normal.sum(0));
status[at[arr[in]]].first++;
at[arr[in]]--;
status[at[arr[in]]].second++;
};
pair<int, int> last = {0, -1};
int ans[maxn];
for (int i = 0; i < q; i++) {
while (arrpii[i].pii.second > last.second) {
last.second++;
add(last.second);
}
while (arrpii[i].pii.first < last.first) {
last.first--;
add(last.first);
}
while (arrpii[i].pii.second < last.second) {
rem(last.second);
last.second--;
}
while (arrpii[i].pii.first > last.first) {
rem(last.first);
last.first++;
}
ans[arrpii[i].in] = curans;
}
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
Compilation message
diversity.cpp: In lambda function:
diversity.cpp:59:15: error: expected primary-expression before 'long'
59 | curans -= long long(at[arr[in]] + 1) * at[arr[in]] / 2;
| ^~~~
diversity.cpp:60:15: error: expected primary-expression before 'long'
60 | curans += long long(at[arr[in]] + 2) * (at[arr[in]] + 1) / 2;
| ^~~~
diversity.cpp: In lambda function:
diversity.cpp:86:15: error: expected primary-expression before 'long'
86 | curans -= long long(at[arr[in]] + 1) * at[arr[in]] / 2;
| ^~~~
diversity.cpp:87:15: error: expected primary-expression before 'long'
87 | curans += long long(at[arr[in]]) * (at[arr[in]] - 1) / 2;
| ^~~~
diversity.cpp: In function 'int main()':
diversity.cpp:10:28: warning: unused variable 'maxq' [-Wunused-variable]
10 | const int maxn = 300005, maxq = 50000;
| ^~~~
