Codeforces 86 D. Powerful array

問題

n項の数列が与えられる。
この数列に対してt個のクエリに答えよ。

クエリ：
整数l,rに対して、次の値を求める。
a[l],a[l+1],...,a[r]における、値sの出現回数をKsとする。
全ての整数sについて、Σs*Ks*ks

制約条件

n,t≦200000
1≦a[i]≦10^6

方針

クエリを並べ替えて処理する。
平方分割っぽいことをする。

lが近いクエリを集めて、rの順にソートすれば、
値の出現回数を求める処理（差分により計算する）はほとんど同じになって計算量が減る。

具体的には(l/500,r)でクエリをソートして処理すればいい。

ソースコード

int n,t,a[200000],le[200000],ri[200000];
pair<pair<int,int>,int> q[200000];
int cnt[1000001];
ll ans[200000];

void run(){
  scanf("%d%d",&n,&t);
  rep(i,n)scanf("%d",a+i);
  rep(i,t){
    int l,r;
    scanf("%d%d",le+i,ri+i);
    q[i]=make_pair(make_pair(--le[i]/500,ri[i]),i);
  }
  sort(q,q+t);
  
  int l=0,r=0;
  ll sum=0;
  rep(i,t){
    int pos=q[i].second, L=le[pos], R=ri[pos];
    while(l<L){
      sum-=cnt[a[l]]*(ll)cnt[a[l]]--*a[l];
      sum+=cnt[a[l]]*(ll)cnt[a[l]]*a[l++];
    }
    while(l>L){
      sum-=cnt[a[--l]]*(ll)cnt[a[l]]++*a[l];
      sum+=cnt[a[l]]*(ll)cnt[a[l]]*a[l];
    }
    while(r<R){
      sum-=cnt[a[r]]*(ll)cnt[a[r]]++*a[r];
      sum+=cnt[a[r]]*(ll)cnt[a[r]]*a[r++];
    }
    while(r>R){
      sum-=cnt[a[--r]]*(ll)cnt[a[r]]--*a[r];
      sum+=cnt[a[r]]*(ll)cnt[a[r]]*a[r];
    }
    ans[pos]=sum;
  }
  rep(i,t)cout<<ans[i]<<endl;
}