Powerful Array

Enes Öncü' ye teşekkür ederiz.

Soru Metni

Size n elemandan oluşan bir dizi ve t adet l ve r ikilisi veriliyor.
Sizden her sorgu için dizinin l ve r aralığındaki altdizisinin Kuvvet Değeri isteniliyor.
Bir altdizideki Kuvvet Değeri şöyle tanımlanıyor:
Bir altdizideki s sayısının geçme sayısı Ks olsun. Tüm farklı s sayıları için Ks*Ks*s toplamı bize altdizinin Kuvvet degerini veriyor.

Size verilen t tane altdizinin Kuvvet Değerlerini ayrı ayrı bulmaniz.

1<=n,t<=200000
Tüm sayılar 1000000'den küçük.

Örnek 1:
3 2
1 2 1
1 2
1 3
Çıktı 1:
3
6

Örnek 2:
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
Çıktı 2:
20
20
20

İkinci örnek ilk sorgu için açıklama:

2. ve 7. indisleri arasında s = 1,2,3 olabiliyor.
Bu aralıkta:
K1 = 3
K2 = 2
K3 = 1 olur.
K1*K1*1+K2*K2*2+K3*K3*3 = 20 olur.

Soru Linki: http://codeforces.com/problemset/problem/86/D

Çözüm metni:

Soruyu çözmeye başlamadan önce tüm sorguları okuyoruz.

Başta tüm sorguları şu şarta göre sıralıyoruz:
a sorgusuyla b sorgusu elimizde olsun.
a -> l1,r1
b -> l2,r2
Eğer diziyi K'lik gruplara ayırdığımızda l1 ve l2 aynı gruptaysa: r1 ve r2 den hangisi küçükse onu daha önce cevaplıyoruz.
Eğer diziyi K'lik gruplara ayırdığımızda l1 ve l2 farklı gruptaysa: l1 ve l2 den küçük olanını önce cevaplıyoruz.

Aslında bundan sonrası amele bir çözüm olacak.

Elimizde sol,sag aralığı ve bu aralıgın cevabı olsun.
Sıradaki sorgu l,r aralığı olsun.

Eğer sağ imleci r den gerideyse sağ imlecini ilerletip cevabı güncelleriz.
Eğer sag imleci r den ilerideyse sağ imlecini geriye çekip cevabı güncelleriz.
Eğer sol imleci l den gerideyse sol imlecini ilerletip cevabı güncelleriz.
Eğer sol imleci l den ilerideyse sol imlecini geriye çekip cevabı güncelleriz.

Peki cevabı nasıl güncelleriz?

Bir dizide şu anda elimizde bulunan sayıların bu aralıkta geçme sayılarını tutarız. Yani her s için bi tane dizide Ks'i tutarız.
Bu diziye P[] diyelim.
Yeni bir eleman x ekleneceğinde cevaptan P[x]*P[x]*x çıkartır P[x]'i 1 artırır son olarak cevaba P[x]*P[x]*x ekleriz.
Altdizideki bir eleman x çıkartılacağında cevaptan P[x]*P[x]*x çıkartır P[x]'i 1 azaltır son olarak cevaba P[x]*P[x]*x ekleriz.

Peki ya maliyet ne oluyor?

Tum K'lık grupları ayrı ayrı inceleyelim.
Bir gurptaki r ler küçükten büyüğe sıralıdır.
Yani sağ imlecini bir grupta toplamda en fazla n kere ilerletebiliriz. Bu da n/K grup için n*n/K olur.
Bir gruptaki herhangi bir l den diğerine geçerken en fazla K işlem yaparız. Bu da t adet sorgu için t*K olur.

Bir gruptan diğer gruba geçerken l imleci en fazla 2*K kadar ilerleyebilir. n/K grup için 2*n maliyet gelir.
Bir gruptan diğer gruba geçerken r imleci en fazla n kadar geriye gelebilir. n/K grup için n*n/K maliyet gelir.

Peki K'yı kaç seçmeliyiz?

n*n/K+t*K yı en küçük yapabilmek için K'yı sqrt(n) seçmeliyiz.

Yani toplamda maliye O( (n+t)*sqrt(n) ) olur.


Çözüm Kodu:

#include <bits/stdc++.h>

#define st first
#define nd second
#define mp make_pair
#define lli long long int
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )

#define sqrtn 450

using namespace std;

int n,t,s[2000000],a[300000];
lli res,ans[300000],sqr[3000000];
pair< pair< int,pair<int,int> >,int > arr[300000];

int main(){

ios_base::sync_with_stdio( false );

cin >> n >> t;
FP( i,1,n ) cin >> a[i],sqr[i]=(lli)i*i;

FP( i,1,t ){
cin >> arr[i].st.nd.nd >> arr[i].st.nd.st,arr[i].nd = i;
arr[i].st.st = (arr[i].st.nd.nd-1)/sqrtn;
}

sort( arr+1,arr+t+1 );

int l=0,r=0;

FP( i,1,t ){
while( r<arr[i].st.nd.st ){
r++;
res -= a[r]*sqr[s[a[r]]];
s[a[r]]++;
res += a[r]*sqr[s[a[r]]];
}
while( r>arr[i].st.nd.st ){
res -= a[r]*sqr[s[a[r]]];
s[a[r]]--;
res += a[r]*sqr[s[a[r]]];
r--;
}
while( l<arr[i].st.nd.nd ){
res -= a[l]*sqr[s[a[l]]];
s[a[l]]--;
res += a[l]*sqr[s[a[l]]];
l++;
}
while( l>arr[i].st.nd.nd ){
l--;
res -= a[l]*sqr[s[a[l]]];
s[a[l]]++;
res += a[l]*sqr[s[a[l]]];
}
ans[arr[i].nd] = res;
}

FP( i,1,t )
cout << ans[i] << endl;

}