/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 300000;
const int A_MAX = 300000;
const int Q_MAX = 50000;
int N, Q;
int A[N_MAX + 2];
int bucketSize;
struct Query {
int l, r;
int id;
};
bool operator < (const Query &a, const Query &b) {
return make_pair((a.l - 1) / bucketSize, a.r) < make_pair((b.l - 1) / bucketSize, b.r);
}
Query queries[Q_MAX + 2];
int occ[A_MAX + 2];
unordered_map <int, int> mp;
void update (int val, int sgn) {
if (--mp[occ[val]] == 0) {
mp.erase(occ[val]);
}
occ[val] += sgn;
mp[occ[val]]++;
}
ll solve () {
vector <pair <int, int>> v;
for (pair <int, int> p : mp) {
v.push_back(p);
}
sort(v.begin(), v.end());
int sum = 0, cnt = 0;
ll sumLR = 0, sumRL = 0;
ll X = 0, Y = 0;
for (pair <int, int> p : v) {
int len, occ; tie(len, occ) = p;
ll u = sumRL - sumLR + (ll) sum * occ; int v = (2 * sum);
int L = min(max((v == 0 ? 0 : (u >= 0 ? u / v : -(-u / v))), (ll) 0), (ll) (occ - 1));
int R = (occ - 1) - L;
for (char c : {'L', 'R'}) {
ll sum1L = (ll) L * (L - 1) / 2, sum2L = (ll) L * (L - 1) * (2 * L - 1) / 6;
Y += len * (sumRL * L + (ll) len * cnt * sum1L + len * (sum2L - sum1L) / 2);
ll aux = 0;
aux += (ll) sum * sum * L;
aux += (ll) 2 * sum * len * sum1L;
aux += (ll) len * len * sum2L;
aux -= X * L + (ll) len * len * sum1L;
aux /= 2;
Y += aux;
X += (ll) len * len * L;
sumLR += (ll) sum * L + len * sum1L;
sumRL += (ll) len * cnt * L + len * sum1L;
sum += (ll) len * L;
cnt += L;
swap(L, R);
swap(sumLR, sumRL);
}
if (sumLR < sumRL) {
Y += sumRL * len + ((ll) sum * sum - X) / 2;
X += (ll) len * len;
sumLR += sum;
sumRL += (ll) len * cnt;
sum += len;
cnt += 1;
} else {
Y += sumLR * len + ((ll) sum * sum - X) / 2;
X += (ll) len * len;
sumRL += sum;
sumLR += (ll) len * cnt;
sum += len;
cnt += 1;
}
}
ll ret = (cnt - 1) * X + 2 * Y;
ret += (ll) sum * (cnt - 1);
ret /= 2;
ret = (ll) cnt * sum * (sum + 1) / 2 - ret;
return ret;
}
ll answer[Q_MAX + 2];
mt19937 rnd (13);
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
bucketSize = max(1, (int) (N / sqrt(Q)));
for (int i = 1; i <= Q; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].id = i;
}
sort(queries + 1, queries + Q + 1);
int l = 1, r = 0;
for (int i = 1; i <= Q; i++) {
while (queries[i].l < l) {
update(A[--l], +1);
}
while (r < queries[i].r) {
update(A[++r], +1);
}
while (l < queries[i].l) {
update(A[l++], -1);
}
while (queries[i].r < r) {
update(A[r--], -1);
}
answer[queries[i].id] = solve();
}
for (int i = 1; i <= Q; i++) {
cout << answer[i] << "\n";
}
return 0;
}
Compilation message
diversity.cpp: In function 'll solve()':
diversity.cpp:61:19: warning: unused variable 'c' [-Wunused-variable]
61 | for (char c : {'L', 'R'}) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
