86D - Powerful array - CodeForces Solution

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)

const int N = 2e5 + 5, M = 1e6 + 5; 

int n, t; 
int a[N], l[N], r[N]; 
ll c[M], ans[N], curr; 
vector <pair<pair<int,int>, int>> v; 

ll get(int x){
    return c[x] * c[x] * x; 
}

void del(int x){
    curr -= get(a[x]); 
    c[a[x]]--; 
    curr += get(a[x]); 
}

void add(int x){
    curr -= get(a[x]); 
    c[a[x]]++; 
    curr += get(a[x]); 
}

int main(){
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    //cin >> n >> t; 
    scanf("%d %d", &n, &t); 
    f(i,1,n+1) //cin >> a[i]; 
        scanf("%d", &a[i]); 
        
    int q = sqrt(n); 

    f(i,0,t){
        //cin >> l[i] >> r[i]; 
        scanf("%d %d", &l[i], &r[i]); 
        v.push_back({{l[i]/q, r[i]}, i}); 
    }

    sort(v.begin(), v.end()); 
    
    int L = 0, R = 0; 

    for(auto p: v){
        int id = p.second; 
        while(L < l[id]) del(L++); 
        while(L > l[id]) add(--L); 
        while(R > r[id]) del(R--); 
        while(R < r[id]) add(++R); 
        ans[id] = curr; 
    }
    f(i,0,t) //cout << ans[i] << "\n"; 
        printf("%I64d\n", ans[i]); 
    return 0; 
}