#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> freq;
vector<int> s;
int val(int a, int b, int c)
{
return a*c*(a+(c-1)*b)+b*b*((((c-1)*c*(2*c-1))/6));
}
int get()
{
int k=0, n=0;
int mod=1;
vector<int> cur;
sort(s.begin(), s.end());
int l=0, r=0, ans=0;
for(auto x: s)
{
int i=x, j=freq[x];
if(j==0) continue;
cur.push_back(i);
k+=j;
n+=(i*j);
}
for(auto x: cur)
{
int i=x, j=freq[x];
if(j==0) continue;
int addleft=(j+mod)/2;
int addright=j-addleft;
ans+=val(l, i, addleft);
ans+=val(n-l-i, -i, addleft);
ans+=val(r, i, addright);
ans+=val(n-r-i, -i, addright);
l+=addleft*i;
r+=addright*i;
mod=(j+mod)%2;
}
s=cur;
return (k*n*(n+1)-n*(k-1)-ans)/2;
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int n, q, b=550, cnt=0; cin>>n>>q;
vector<int> a(n), ans(q);
vector<array<int, 3>> query[n/b+2];
for(int i=0; i<n; i++) cin>>a[i];
while(q--)
{
int l, r; cin>>l>>r;
l--; r--;
query[l/b].push_back({r, l, ++cnt});
}
int l=0, r=-1;
vector<int> count(3000005);
for(int i=0; i<n/b+1; i++)
{
sort(query[i].begin(), query[i].end());
for(auto x: query[i])
{
swap(x[0], x[1]);
while(x[0]>l)
{
count[a[l]]--;
if(count[a[l]]!=0)
freq[count[a[l]]]++;
freq[count[a[l]]+1]--;
if(freq[count[a[l]]]==1&&count[a[l]]!=0) s.push_back(count[a[l]]);
l++;
}
while(x[0]<l)
{
l--;
count[a[l]]++;
freq[count[a[l]]]++;
if(freq[count[a[l]]-1]>0)
freq[count[a[l]]-1]--;
if(freq[count[a[l]]]==1&&count[a[l]]!=0) s.push_back(count[a[l]]);
}
while(x[1]<r)
{
if(count[a[r]]!=0)
freq[count[a[r]]]--;
count[a[r]]--;
freq[count[a[r]]]++;
if(freq[count[a[r]]]==1&&count[a[r]]!=0) s.push_back(count[a[r]]);
r--;
}
while(x[1]>r)
{
r++;
if(count[a[r]]!=0)
freq[count[a[r]]]--;
count[a[r]]++;
freq[count[a[r]]]++;
if(freq[count[a[r]]]==1&&count[a[r]]!=0) s.push_back(count[a[r]]);
}
ans[x[2]-1]=get();
}
}
for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
}
Compilation message
diversity.cpp: In function 'int32_t main()':
diversity.cpp:135: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]
135 | for(int i=0; i<ans.size(); i++) cout<<ans[i]<<"\n";
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
23788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
