Hi guys
I was solving the problem 86D — Powerful Array using Mo's algorithm. But I get TLE.
Someone can help me?
My solution
Cod
/*input
3 2
1 2 1
1 2
1 3
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.rbegin(), x.rend()
#define sz(x) (int) x.size()
#define pb push_back
#define fst first
#define snd second
typedef string st;
typedef long long ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <int,int> ii;
typedef pair <int, ii> iii;
int block;
#define maxn 1000005
#define maxf 200004
struct Mo{
int l, r, id;
Mo(){}
Mo(int l, int r, int id){
this->l = l, this->r = r, this->id = id;
}
bool operator < (const Mo o){
if(l/block != o.l/block)
return l/block < o.l/block;
return r < o.r;
}
};
int see[maxf];
ll ans[maxf], v[maxf], freq[maxn];;
Mo q[maxf];
ll resp;
void update(int x){
if(!see[x]){
resp -= (freq[v[x]]*freq[v[x]])*v[x];
freq[v[x]]++;
resp += (freq[v[x]]*freq[v[x]])*v[x];
}
else{
resp -= (freq[v[x]]*freq[v[x]])*v[x];
freq[v[x]]--;
resp += (freq[v[x]]*freq[v[x]])*v[x];
}
see[x] ^= 1;
}
int main(){
int n, t, x, y;
scanf("%d %d", &n, &t);
block = sqrt(n);
for(int i = 0; i < n; i++)
scanf("%lld", v+i);
for(int i = 0; i < t; i++){
scanf("%d %d", &x, &y);
q[i] = {x, y, i};
}
sort(q, q+t);
int L = 0, R = 0;
resp = 0;
for(int i = 0; i < t; i++){
int l = q[i].l-1, r = q[i].r-1;
int id = q[i].id;
while(L < l)
update(L++);
while(L > l)
update(--L);
while(R <= r)
update(R++);
while(R > r+1)
update(--R);
ans[id] = resp;
}
for(int i = 0; i < t; i++)
printf("%I64d\n", ans[i]);
return 0;
}