莫队

  1. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 5e5+100;
  6. const int maxm =1e6+100;
  7. ll re[maxm];
  8. ll a[maxn],anss[maxn];
  9. struct query{
  10.     ll l,r,id;
  11.     ll ans;
  12. }e[maxn];
  13. ll ans,bl;
  14. inline int read()
  15. {
  16.      int k=0;
  17.      char c;
  18.      c=getchar();
  19.      while(!isdigit(c))c=getchar();
  20.      while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();}
  21.      return k;
  22. }
  23. void remove(int pos){
  24.     ans-=a[pos]*((re[a[pos]]*re[a[pos]])-(re[a[pos]]-1)*(re[a[pos]]-1));
  25.     re[a[pos]]--;
  26. }
  27. void add(int pos){
  28.      ans+=a[pos]*(-(re[a[pos]]*re[a[pos]])+(re[a[pos]]+1)*(re[a[pos]]+1));
  29.      ++re[a[pos]];
  30. }
  31. bool cmp1(query a,query b){
  32.     return (a.l/bl==b.l/bl)?a.r<b.r:a.l<b.l;
  33. }
  34. bool cmp2(query a,query b){
  35.     return a.id<=b.id;
  36. }
  37. int n,m,i;
  38. int main(){
  39.     //freopen("1.in","r",stdin);
  40.     scanf("%d %d",&n,&m);
  41.     for(i=1;i<=n;i++) scanf("%lld",&a[i]);
  42.     for(i=1;i<=m;i++){
  43.         scanf("%lld %lld",&e[i].l,&e[i].r);
  44.         e[i].id=i;
  45.     }
  46.     bl=sqrt(n);
  47.     sort(e+1,e+m+1,cmp1);
  48.     ans=0;
  49.     int L,R;
  50.     int curl=1;int curr=0;
  51.     for(i=1;i<=m;i++){
  52.         L=e[i].l;R=e[i].r;
  53.         while(curl<L) remove(curl++);
  54.         while(curl>L) add(--curl);
  55.         while(curr>R) remove(curr--);
  56.         while(curr<R) add(++curr);
  57.         anss[e[i].id]=ans;
  58.     }
  59.     for(i=1;i<=m;i++){
  60.        printf("%lld\n",anss[i]);
  61.     }
  62.     return 0;
  63. }
  65. //O(nlog(n))