#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using i64 = std::int64_t;
constexpr int B = 1000;
constexpr int MAX = 300000;
constexpr i64 sum_k(const int n) {
return (i64)n * (n + 1) / 2;
}
constexpr i64 sum_k2(const int n) {
return (i64)n * (n + 1) * (2 * n + 1) / 6;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, Q;
std::cin >> N >> Q;
vector<int> A(N);
for (auto& x : A) {
std::cin >> x;
x -= 1;
}
const int G = N / B;
vector precalc(G, vector<vector<pair<int, int>>>(G + 1));
for (int lc = 0; lc < G; ++lc) {
vector<char> appear(MAX);
vector<int> count(MAX);
for (int rc = lc + 1; rc <= G; ++rc) {
vector<int> remove, add;
for (int i = B * (rc - 1); i < B * rc; ++i) {
if (!appear[A[i]]) {
appear[A[i]] = true;
if (count[A[i]] > 0) {
remove.push_back(count[A[i]]);
}
add.push_back(A[i]);
}
count[A[i]] += 1;
}
for (auto& x : add) {
appear[x] = false;
x = count[x];
}
std::sort(remove.begin(), remove.end());
std::sort(add.begin(), add.end());
const auto& read = precalc[lc][rc - 1];
auto& write = precalc[lc][rc];
const int A = read.size(), B = remove.size(), C = add.size();
int i = 0, j = 0, k = 0;
while (i < A or k < C) {
int val = MAX;
if (i < A) {
val = std::min(val, read[i].first);
}
if (k < C) {
val = std::min(val, add[k]);
}
int cnt = 0;
if (i < A and val == read[i].first) {
cnt += read[i].second;
i += 1;
}
while (j < B and val == remove[j]) {
j += 1;
cnt -= 1;
}
while (k < C and val == add[k]) {
k += 1;
cnt += 1;
}
if (cnt > 0) {
write.emplace_back(val, cnt);
}
}
}
}
vector<vector<int>> idx(MAX);
for (int i = 0; i < N; ++i) {
idx[A[i]].push_back(i);
}
const auto range_count = [&](const int l, const int r, const int x) {
const auto& v = idx[x];
return std::lower_bound(v.begin(), v.end(), r) - std::lower_bound(v.begin(), v.end(), l);
};
vector<char> appear(MAX);
vector<int> count(MAX);
while (Q--) {
int l, r;
std::cin >> l >> r;
l -= 1;
vector<pair<int, int>> list;
if (l / B == r / B) {
vector<int> add;
for (int i = l; i < r; ++i) {
if (!appear[A[i]]) {
appear[A[i]] = true;
add.push_back(A[i]);
}
count[A[i]] += 1;
}
for (const int x : add) {
appear[x] = false;
list.emplace_back(count[x], 1);
count[x] = 0;
}
std::sort(list.begin(), list.end());
} else {
const int lc = (l + B - 1) / B;
const int rc = r / B;
asserr(lc <= rc);
vector<int> remove, add, seen;
for (int i = l; i < B * lc; ++i) {
if (!appear[A[i]]) {
appear[A[i]] = true;
const int tmp = range_count(B * lc, B * rc, A[i]);
if (tmp > 0) {
remove.push_back(tmp);
}
add.push_back(range_count(l, r, A[i]));
seen.push_back(A[i]);
}
}
for (int i = B * rc; i < r; ++i) {
if (!appear[A[i]]) {
appear[A[i]] = true;
const int tmp = range_count(B * lc, B * rc, A[i]);
if (tmp > 0) {
remove.push_back(tmp);
}
add.push_back(range_count(l, r, A[i]));
seen.push_back(A[i]);
}
}
for (const int x : seen) {
appear[x] = false;
}
std::sort(remove.begin(), remove.end());
std::sort(add.begin(), add.end());
const auto& read = precalc[lc][rc];
const int A = read.size(), B = remove.size(), C = add.size();
int i = 0, j = 0, k = 0;
while (i < A or k < C) {
int val = MAX;
if (i < A) {
val = std::min(val, read[i].first);
}
if (k < C) {
val = std::min(val, add[k]);
}
int cnt = 0;
if (i < A and val == read[i].first) {
cnt += read[i].second;
i += 1;
}
while (j < B and val == remove[j]) {
j += 1;
cnt -= 1;
}
while (k < C and val == add[k]) {
k += 1;
cnt += 1;
}
if (cnt > 0) {
list.emplace_back(val, cnt);
}
}
}
const int len = r - l;
i64 ans = sum_k(len);
const auto add_to = [&](const i64 s, const int a, const int n) {
ans += (n * s + sum_k(n) * a) * len;
ans -= n * s * s + 2 * s * sum_k(n) * a + sum_k2(n) * a * a;
};
int left = 0, right = 0;
for (const auto& [a, b] : list) {
if (left > right) {
std::swap(left, right);
}
const int need = std::min(b, (right - left + a - 1) / a);
const int to_left = need + (b - need) / 2;
const int to_right = b - to_left;
add_to(left, a, to_left);
add_to(right, a, to_right);
left += a * to_left;
right += a * to_right;
}
ans -= (i64)left * (len - left);
std::cout << ans << '\n';
}
return 0;
}
Compilation message
diversity.cpp: In function 'int main()':
diversity.cpp:118:13: error: 'asserr' was not declared in this scope; did you mean 'assert'?
118 | asserr(lc <= rc);
| ^~~~~~
| assert
