#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
const int Q = 5e4 + 11;
const int B = 450;
long long solve(vector<pair<int, int>> c) {
sort(c.rbegin(), c.rend());
int n = 0, k = 0;
deque<pair<int, int>> q;
int t = 0;
for (const auto &[x, y] : c) {
n += x * y;
k += y;
if (t) {
q.push_back({x, (y + 1) / 2});
if (y > 1)
q.push_front({x, y / 2});
} else {
q.push_front({x, (y + 1) / 2});
if (y > 1)
q.push_back({x, y / 2});
}
t = (t + y) & 1;
}
vector<pair<int, int>> z(q.begin(), q.end());
long long all = n * 1ll * (n + 1) / 2 * k;
long long bad = 0;
long long sum = 0;
for (int i = 0; i < (int) z.size(); ++i) {
const auto &[x, y] = z[i];
bad += sum * sum * y;
bad += sum * x * y * (y - 1);
bad += sum * y;
bad += x * 1ll * y * (y - 1) / 2;
bad += (y - 1) * 1ll * y * (2 * (y - 1) + 1) / 6 * x * x;
sum += x * y;
}
sum = 0;
for (int i = (int) z.size() - 1; i >= 0; --i) {
const auto &[x, y] = z[i];
bad += sum * sum * y;
bad += sum * x * y * (y - 1);
bad += sum * y;
bad += x * 1ll * y * (y - 1) / 2;
bad += (y - 1) * 1ll * y * (2 * (y - 1) + 1) / 6 * x * x;
sum += x * y;
}
bad /= 2;
// cout << all << " " << bad << "\n";
long long res = all - bad;
return res;
}
int n, q;
int a[N];
int l[Q], r[Q];
int ord[Q];
struct Cnt {
int cnt[N];
int scnt[N];
bool used[N];
vector<int> s;
void add(int x) {
++cnt[x];
if (++scnt[cnt[x]] == 1 && !used[cnt[x]] && cnt[x] > 0) {
s.push_back(cnt[x]);
used[cnt[x]] = true;
}
}
void remove(int x) {
--cnt[x];
if (++scnt[cnt[x]] == 1 && !used[cnt[x]] && cnt[x] > 0) {
s.push_back(cnt[x]);
used[cnt[x]] = true;
}
}
vector<pair<int, int>> get_cnts() {
vector<pair<int, int>> res;
vector<int> s1;
for (int i : s) {
if (scnt[i] > 0) {
res.push_back({i, scnt[i]});
s1.push_back(i);
} else {
used[i] = false;
}
}
s = s1;
return res;
}
Cnt() {
for (int i = 0; i < N; ++i) {
++scnt[cnt[i]];
}
s.reserve(N);
}
} cnt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for (int i = 0; i < q; ++i) {
cin >> l[i] >> r[i];
--l[i];
}
iota(ord, ord + q, 0);
sort(ord, ord + q, [&] (const int &i, const int &j) {
int blocki = l[i] / B;
int blockj = l[j] / B;
return make_pair(blocki, (blocki & 1) ? -r[i] : r[i]) < make_pair(blockj, (blockj & 1) ? -r[j] : r[j]);
});
vector<long long> ans(q);
int cl = 0, cr = 0;
for (int i = 0; i < q; ++i) {
while (cl > l[ord[i]]) {
cnt.add(a[--cl]);
}
while (cr < r[ord[i]]) {
cnt.add(a[cr++]);
}
while (cl < l[ord[i]]) {
cnt.remove(a[cl++]);
}
while (cr > r[ord[i]]) {
cnt.remove(a[--cr]);
}
ans[ord[i]] = solve(cnt.get_cnts());
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
