fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long mod = 1e9 + 7;
  4. const double eps = 1e-9;
  5. const double PI = atan(1.0);
  6. #define readFile freopen("input","r",stdin);
  7. #define writeFile freopen("output","w",stdout);
  8. #define fastIO ios::sync_with_stdio(0);
  9. typedef pair<int,int> ii;
  10. typedef unsigned long long ULL;
  11. const int N = 200001;
  12.  
  13. int arr[N];
  14. int bsize;
  15. struct query{
  16.     long long ord,bucket,l,r;
  17.     query(){}
  18.     query(int ord,int l,int r){
  19.         this->ord = ord;
  20.         this->l = l;
  21.         this->r = r;
  22.         this->bucket = ord/bsize;
  23.         if (!this->bucket) this->bucket++; 
  24.     }
  25. }queries[N];
  26. struct cmp{
  27.     bool operator () (query q1,query q2){
  28.         if (q1.bucket!=q2.bucket) return q1.r<q2.r;
  29.         return q1.bucket<q2.bucket;
  30.     }
  31. };
  32.  
  33. int main(){
  34. #ifndef ONLINE_JUDGE
  35.     readFile;
  36. #endif
  37.     fastIO;
  38.     long long n,q; cin>>n>>q;
  39.     bsize = sqrt(N);
  40.     long long res[N];
  41.     for(int i=0;i<n;i++) cin>>arr[i];
  42.     for(int i=0;i<q;i++){
  43.         long long a,b; cin>>a>>b;
  44.         a--;
  45.         queries[i] = query(i,a,b);
  46.     }
  47.     sort(queries,queries+q,cmp());
  48.     long long l=queries[0].l,r=l=queries[0].l;
  49.     unsigned long long ans = 0;
  50.     long long rep[1000001];
  51.     memset(rep,0,sizeof(rep));
  52.     for(int i=0;i<q;i++){
  53.         long long ll=queries[i].l,rr = queries[i].r;
  54.         while (l<ll){
  55.             long long t = rep[arr[l]]--;
  56.             ans-=(t*t-(t-1)*(t-1))*arr[l];
  57.             l++;
  58.         }
  59.         while (l>ll){
  60.             long long t = ++rep[arr[l-1]];
  61.             ans+=(t*t-(t-1)*(t-1))*arr[l-1];
  62.             l--;
  63.         }    
  64.         while (r>rr){
  65.             long long t = rep[arr[r-1]]--;
  66.             ans-=(t*t-(t-1)*(t-1))*arr[r-1];
  67.             r--;
  68.         }
  69.         while (r<rr){
  70.             long long t = ++rep[arr[r]];
  71.             ans+=(t*t-(t-1)*(t-1))*arr[r];
  72.             r++;
  73.         }
  74.         res[queries[i].ord] = ans;
  75.     }
  76.     for(int i=0;i<q;i++) cout<<res[i]<<"\n";
  77. }
Runtime error #stdin #stdout 0s 10496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/di5s3q
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!