This is my solution for 86D — Powerful Array.

#include<bits/stdc++.h> #define MAXN 200010 #define MAXX 1000010 using namespace std; int block; long long arr[MAXN+1],freq[MAXX+1],sol[MAXN+1]; struct query{ int l,r,i; }qry[MAXN+1]; bool comp(query q1,query q2){ if(q1.l!=q2.l) return (q1.l/block)<(q2.l/block); return (q1.r/block)<(q2.r/block); } int main(){ ios::sync_with_stdio(false); int n,t,l,r,lx,rx; long long x=0; cin>>n>>t; block=sqrt(n); for(int i=0;i<n;i++) cin>>arr[i]; for(int i=0;i<t;i++){ cin>>qry[i].l>>qry[i].r; qry[i].l--; qry[i].r--; qry[i].i=i; } sort(qry,qry+t,comp); l=0; r=-1; for(int i=0;i<t;i++){ lx=qry[i].l; rx=qry[i].r; while(l>lx){ l--; x+=(((2LL*freq[arr[l]])+1)*arr[l]); freq[arr[l]]++; } while(l<lx){ x-=(((2LL*freq[arr[l]])-1)*arr[l]); freq[arr[l]]--; l++; } while(r<=rx){ x+=(((2LL*freq[arr[r]])+1)*arr[r]); freq[arr[r]]++; r++; } while(r>(rx+1)){ r--; x-=(((2LL*freq[arr[r]])-1)*arr[r]); freq[arr[r]]--; } sol[qry[i].i]=x; } for(int i=0;i<t;i++) cout<<sol[i]<<"\n"; return 0; }

This gave me a TLE at test case 6 taking more than 5000 ms whereas most AC solutions pass at 800-1000 ms. How do I optimize my code?