| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 814828 | khshg | Diversity (CEOI21_diversity) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int maxn = 300000, maxq = 50000;
int B;
int N, Q;
int A[maxn], cnt[maxn], l[maxn + 1], r[maxn + 1];
ar<int, 3> q[maxn];
ll cur, ans[maxq];
ar<ll, maxn + 1> pref, LtoR, RtoL;
void add(ar<ll, maxn + 1>& a, int i, ll val) {
++i;
while(i <= maxn) {
a[i] += val;
i += i & -i;
}
}
ll sum(ar<ll, maxn + 1>& a, int p) {
ll ans = 0;
while(p) {
ans += a[p];
p -= p & -p;
}
return ans;
}
ll sum(ar<ll, maxn + 1>& a, int l, int r) {
return sum(a, r + 1) - sum(a, l);
}
int prv(int x) {
if(x <= (N - 1) / 2) return N - x;
else return N - x - 1;
}
int nxt(int x) {
if(x <= N / 2) return N - x - 1;
else return N - x;
}
void add(int i) {
int v = A[i];
i = r[cnt[v]];
assert(i >= 0 && i < N);
if(l[cnt[v]] == r[cnt[v]]) {
l[cnt[v]] = r[cnt[v]] = -1;
} else {
r[cnt[v]] = prv(i);
}
cur += ++cnt[v];
if(i + 1 <= N - 1) cur += sum(LtoR, i + 1, N - 1) - sum(pref, i + 1, N - 1) * i;
if(0 <= i - 1) cur += sum(RtoL, 0, i - 1) - sum(pref, 0, i - 1) * (N - 1 - i);
add(LtoR, i, i + 1);
add(RtoL, i, N - i);
add(pref, i, 1);
if(l[cnt[v]] == -1) l[cnt[v]] = r[cnt[v]] = i;
else l[cnt[v]] = i;
}
void rem(int i) {
int v = A[i];
i = l[cnt[v]];
if(l[cnt[v]] == r[cnt[v]]) {
l[cnt[v]] = r[cnt[v]] = -1;
} else {
l[cnt[v]] = nxt(i);
}
cur -= cnt[v]--;
if(i + 1 <= N - 1) cur -= sum(LtoR, i + 1, N - 1) - sum(pref, i + 1, N - 1) * i;
if(0 <= i - 1) cur -= sum(RtoL, 0, i - 1) - sum(pref, 0, i - 1) * (N - 1 - i);
add(LtoR, i, -(i + 1));
add(RtoL, i, -(N - i));
add(pref, i, -1);
if(l[cnt[v]] == -1) l[cnt[v]] = r[cnt[v]] = i;
else r[cnt[v]] = i;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
B = N / max(1, sqrt(Q));
l[0] = 0;
r[0] = N / 2;
for(int i = 0; i < N; ++i) {
l[i + 1] = r[i + 1] = -1;
cin >> A[i];
--A[i];
}
for(int i = 0; i < Q; ++i) {
for(int x : {0, 1}) { cin >> q[i][x]; --q[i][x]; }
q[i][2] = i;
}
sort(q, q + Q, [&](const ar<int, 3>& a, const ar<int, 3>& b) {
if(a[0] / B == b[0] / B) return (a[1] < b[1]);
return ((a[0] / B) < (b[0] / B));
});
for(int i = 0, L = 0, R = 0; i < Q; ++i) {
int ql = q[i][0], qr = q[i][1];
while(R <= qr) add(R++);
while(L < ql) rem(L++);
while(L > ql) add(--L);
while(R > qr + 1) rem(--R); // erkhes sussy
ans[q[i][2]] = cur;
}
for(int i = 0; i < Q; ++i) {
cout << ans[i] << '\n';
}
return 0;
}