#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
//typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
const int MAXN = 3e5+5,blk = 450;
int a[MAXN];
struct que{
int l,r,id;
que(){}
que(int _l,int _r,int _id):l(_l),r(_r),id(_id){}
bool operator<(const que &q){
if((l+blk-1)/blk &1)return make_pair((l+blk-1)/blk,r) < make_pair((q.l+blk-1)/blk,q.r);
return make_pair((l+blk-1)/blk,-r) < make_pair((q.l+blk-1)/blk,-q.r);
}
};
int cnt[MAXN],freq[MAXN];
set<int>s;
void add(int x,int c){
if(freq[cnt[x]] == 1)s.erase(cnt[x]);
freq[cnt[x]]--;
cnt[x]+=c;
freq[cnt[x]]++;
if(freq[cnt[x]] == 1)s.insert(cnt[x]);
}
typedef __int128 ll;
ll cal(ll n){
vector<ll>v;
ll T = 0;
for(int x:s){
v.pb(x);
T+=freq[x];
}
int t = sz(v);
vector<int>in(t,0);
//ans = 1/2(T*n*n + n - sum of squares)
//for(int x:v)cout<<x<<" ";cout<<'\n';
//for(int x:v)cout<<freq[x]<<" ";cout<<'\n';
ll res = 0,cur = 0;
for(int i=1;i<t;i++){
in[i] = in[i-1]+(freq[v[i]]&1);
in[i]%=2;
}
//S = (cur+v)^2 + (cur+2v)^2 + ... + (cur+xv)^2
// = x*cur*cur - 2cur*v(1+2+...+x) + v^2(1^2+2^2+3^2...x2);
//(n-cur-v)^2 + (n-cur-2v)^2 + ... + (n-cur-xv)^2;
//= x*n*n - 2*n( x*cur + v+2v+3v..+xv) + S
vector<ll>tmp;
for(int i=0;i<t;i++){
ll x = (freq[v[i]]+1)/2 - (in[i]==0);
/*
ll y = x*(x+1)/2;
ll z = (x*(x+1)*(2*x+1))/6;
ll S = 0;
S+=x*cur*cur;
S+=2*cur*v[i]*y;
S+=v[i]*v[i]*z;
res-=x*n*n;
res+=2*n*( x*cur + y*v[i]);
res-=2*S;
cur+=x*v[i];*/
for(int j=0;j<x;j++)tmp.pb(v[i]);
}
for(int i=t-1;i>=0;i--){
ll x = (freq[v[i]]+1)/2 - (in[i]==0);
x = freq[v[i]]-x;
/*
ll y = x*(x+1)/2;
ll z = (x*(x+1)*(2*x+1))/6;
ll S = 0;
S+=x*cur*cur;
S+=2*cur*v[i]*y;
S+=v[i]*v[i]*z;
assert(S>=0);
res-=x*n*n;
res+=2*n*( x*cur + y*v[i]);
res-=2*S;
cur+=x*v[i];
* */
for(int j=0;j<x;j++)tmp.pb(v[i]);
}
for(ll x:tmp){
cur+=x;
res-=cur*cur;
res-=(n-cur)*(n-cur);
}
res+=T*n*n+n;
res+=n*n;
return res/2;
}
int main()
{
owo
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
vector<que>qq(q);
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
qq[i] = que(l,r,i);
}
sort(all(qq));
vector<ll>ans(q);
int L = 1,R = 0;
for(int i=0;i<q;i++){
int l = qq[i].l;
int r = qq[i].r;
while(L>l){
L--;
add(a[L],1);
}
while(L<l){
add(a[L],-1);
L++;
}
while(R<r){
R++;
add(a[R],1);
}
while(R>r){
add(a[R],-1);
R--;
}
//cout<<"TES"<<'\n';
ans[qq[i].id] = cal(r-l+1);
}
for(int i=0;i<q;i++){
long long int x = ans[i];
cout<<x<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
