#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 3e5;
const int c = 1;
const int bsize = 550;
struct qry
{
int st, dr, poz;
};
int n,q;
int v[nmax + 5];
int fr[nmax + 5];
int nrfr[nmax + 5];
int st[nmax + 5], dr[nmax + 5];
vector<int> l, h;
int sp[c + 5][nmax + 5];
vector<qry> B[bsize + 5];
int sum_prod(int p, int st, int dr)
{
if(st - p <= 0)
{
return sp[p][dr];
}
return sp[p][dr] - sp[p][st - p];
}
int solve_heavy(int x, int y)
{
deque<int> d;
for(int i=0; i<h.size(); i++)
{
if(i % 2 == 0)
{
d.push_back(h[i]);
}
else
{
d.push_front(h[i]);
}
}
int sum_st = 0, sum_dr = 0;
for(int i=1; i<=c; i++)
{
sum_st += st[i] * i;
sum_dr += dr[i] * i;
}
for(auto it : d)
{
sum_dr += it;
}
int rez = 0;
for(auto it : d)
{
sum_dr -= it;
rez += 1LL * (y - x + 1) * (y - x + 2) / 2;
rez -= 1LL * sum_st * (sum_st + 1) / 2;
rez -= 1LL * sum_dr * (sum_dr + 1) / 2;
sum_st += it;
}
return rez;
}
int solve_light(int x, int y)
{
int rez = 0;
int sum_dr = 0, sum_st = 0;
for(int i=1; i<=c; i++)
{
sum_dr += dr[i] * i;
sum_dr += st[i] * i;
}
for(auto it : h)
{
sum_dr += it;
}
for(int i=1; i<=c; i++)
{
int cnt = st[i];
rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
rez -= sum_prod(i, sum_st, sum_st + i * (cnt - 1));
rez -= sum_prod(i, sum_dr - i * cnt, sum_dr - i);
sum_st += st[i] * i;
sum_dr -= st[i] * i;
}
sum_dr = 0, sum_st = 0;
for(int i=1; i<=c; i++)
{
sum_st += st[i] * i;
sum_st += dr[i] * i;
}
for(auto it : h)
{
sum_st += it;
}
for(int i=1; i<=c; i++)
{
int cnt = dr[i];
rez += 1LL * (1LL * (y - x + 1) * (y - x + 2) / 2) * cnt;
rez -= sum_prod(i, sum_st - i * cnt, sum_st - i);
rez -= sum_prod(i, sum_dr, sum_dr + i * (cnt - 1));
sum_st -= dr[i] * i;
sum_dr += dr[i] * i;
}
return rez;
}
int query(int x, int y)
{
int nr = h.size();
for(int i=1; i<=c; i++)
{
if(nrfr[i]==0)
{
st[i] = dr[i] = 0;
continue;
}
if(nrfr[i] % 2 == 0)
{
st[i] = dr[i] = nrfr[i] / 2;
}
else
{
if(nr % 2 == 0)
{
st[i] = nrfr[i] / 2;
dr[i] = nrfr[i] / 2 + 1;
}
else
{
st[i] = nrfr[i] / 2 + 1;
dr[i] = nrfr[i] / 2;
}
}
nr += nrfr[i];
}
int rez = 0;
rez += solve_heavy(x,y);
rez += solve_light(x,y);
return rez;
}
void Add(int val)
{
--nrfr[fr[val]];
++fr[val];
++nrfr[fr[val]];
if(fr[val] > c)
{
l.push_back(val);
}
}
void Remove(int val)
{
--nrfr[fr[val]];
--fr[val];
++nrfr[fr[val]];
}
void build_h()
{
vector<int> aux;
h.clear();
for(auto it : l)
{
if(fr[it] > c)
{
aux.push_back(it);
h.push_back(fr[it]);
}
}
l = aux;
sort(h.begin(),h.end(),greater<int>());
}
void precalc()
{
for(int p=1; p<=c; p++)
{
for(int i=1; i<=n; i++)
{
sp[p][i] = 1LL * i * (i + 1) / 2;
if(i - p > 0)
{
sp[p][i] += sp[p][i - p];
}
}
}
}
int get_bucket(int poz)
{
return (poz - 1) / bsize + 1;
}
bool cmp(qry a, qry b)
{
return (a.dr < b.dr);
}
int rez[nmax + 5];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif // home
cin>>n>>q;
for(int i=1; i<=n; i++)
{
cin>>v[i];
}
precalc();
for(int i=1; i<=q; i++)
{
qry x;
cin>>x.st>>x.dr;
x.poz = i;
int bucket = get_bucket(x.st);
B[bucket].push_back(x);
}
for(int b=1;b<=bsize+1;b++)
{
if(!B[b].size())
{
continue;
}
sort(B[b].begin(), B[b].end(),cmp);
int last_st = B[b].front().st, last_dr = B[b].front().st - 1;
for(auto it : B[b])
{
int st = it.st;
int dr = it.dr;
int poz = it.poz;
for(int i=last_dr+1;i<=dr;i++)
{
Add(v[i]);
}
if(last_st < st)
{
for(int i=last_st;i<st;i++)
{
Remove(v[i]);
}
}
else
{
for(int i=st;i<last_st;i++)
{
Add(v[i]);
}
}
build_h();
rez[poz] = query(st,dr);
last_st = st, last_dr = dr;
}
l.clear();
for(int i=1;i<=nmax;i++)
{
nrfr[i] = 0;
fr[i] = 0;
}
}
for(int i=1;i<=q;i++)
{
cout<<rez[i]<<'\n';
}
return 0;
}
Compilation message
diversity.cpp: In function 'long long int solve_heavy(long long int, long long int)':
diversity.cpp:42:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0; i<h.size(); i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
