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 <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
const int mx = 300'000;
const int mxQ = 50'000;
const int rt = 500;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define sz(x) (int(x.size()))
int N, Q;
vi a(1+mx);
vi l(1+mxQ), r(1+mxQ);
vll ans(1+mxQ);
int L = 1;
int R = 0;
vll ct(1+mx, 0);
vll freq(1+mx, 0);
vector<ll> sizes;
vector<bool> occ(1+mx, 0);
ll ap_sum(ll a, ll d, ll n)
{
return (n * (2*a + (n-1)*d))/2;
}
ll ap_sq_sum(ll a, ll d, ll n)
{
return n*a*a + a*d*(n-1)*n + d*d*(((n-1)*n*(2*n-1))/6);
}
ll get_ans()
{
vector<ll> sizes2;
for(ll s: sizes)
{
if(occ[s]) continue;
if(freq[s] == 0) continue;
sizes2.push_back(s);
occ[s] = 1;
}
sizes = sizes2;
for(ll s: sizes) occ[s] = 0;
sort(sizes.begin(), sizes.end(), [] (int u, int v)
{
return u > v;
});
deque< pair<ll, ll> > ord;
int z = 0;
for(ll s: sizes)
{
if(freq[s] % 2 == 1)
{
// cerr << "odd!\n";
if(z) ord.push_back({s, 1});
else ord.push_front({s, 1});
z = !z;
}
if(freq[s]/2)
{
// cerr << "breaking into 2\n";
ord.push_back({s, freq[s]/2});
ord.push_front({s, freq[s]/2});
}
}
ord.push_front({0, 0});
ll ans = 0;
ll tot = 0;
int P = sz(ord) - 1;
vll prefsum(1+P, 0);
for(int i = 1; i <= P; i++)
{
prefsum[i] = prefsum[i-1] + (ord[i].first * ord[i].second);
}
tot = prefsum[P];
for(int i = 1; i <= P; i++)
{
ans += ord[i].second * (ord[i].first * (ord[i].first + 1))/2;
ans += ord[i].second * (ord[i].first * (tot - ord[i].first));
ans += (tot - ord[i].first) * ap_sum(prefsum[i-1], ord[i].first, ord[i].second);
ans -= ap_sq_sum(prefsum[i-1], ord[i].first, ord[i].second);
}
return ans;
}
void add_species(int a)
{
freq[ct[a]]--;
ct[a]++;
freq[ct[a]]++;
sizes.push_back(ct[a]);
}
void remove_species(int a)
{
freq[ct[a]]--;
ct[a]--;
freq[ct[a]]++;
sizes.push_back(ct[a]);
}
void expand_right()
{
R++;
add_species(a[R]);
}
void expand_left()
{
L--;
add_species(a[L]);
}
void contract_right()
{
remove_species(a[R]);
R--;
}
void contract_left()
{
remove_species(a[L]);
L++;
}
int main()
{
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int j = 1; j <= Q; j++) cin >> l[j] >> r[j];
vi I(Q);
for(int j = 0; j < Q; j++) I[j] = j+1;
sort(I.begin(), I.end(), [] (int u, int v)
{
if(l[u]/rt != l[v]/rt) return l[u]/rt < l[v]/rt;
else return r[u] < r[v];
});
freq[0] = mx;
for(int q: I)
{
while(R < r[q]) expand_right();
while(L > l[q]) expand_left();
while(R > r[q]) contract_right();
while(L < l[q]) contract_left();
ans[q] = get_ans();
}
for(int q = 1; q <= Q; q++) cout << ans[q] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |