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;
}
```

block = sqrt(n), should be block = sqrt(maxn) in this case, as you are reasoning on the frequency of each element on the array, not the array it self.

Can you explain?Bcz block size is for Queries.So how it is related to freq

Also, I learnt this thing from teja349: If L1 and L2 lie in the same block, you check the parity of the block. If the parity is even, then you sort according to increasing R or else you sort according to decreasing R. This reduces runtime to half and is quite enough to get AC on this problem.

My AC submission using this trick: http://codeforces.com/contest/86/submission/28243471 (Sorry for the incredibly ill-named variables)

Thank you, ista2000. I got acc using this trick. I will write this trick in my notebbok :P!

Nice

@MagicPotato can you please explain why "if the parity is even, then you sort according to increasing R or else you sort according to decreasing R" would reduce the runtime to half ? Thanks in advance.

You will traverse the groups in this sort of pattern:

/\ /

/ \ /

/ \ /

/ \/

Instead of this one:

/| /| /|

/ | / | / |

/ | / | / |

/ |/ |/ |

Thus if you count each dash as one iteration, you can easily see you would need approx. twice the number of iterations, which on a tightly time bound problem such as this one would lead to a TLE.

never seen a person naming a variable "_" !!!

You can also try with ceil (sqrt (n)) . It worked for me . @gaurav172 taught me this .

your update function can be optimized to run much more efficiently. I tried this in java and on 9th attempt got it to work.35944895 3 methods. solve, add and remove to make it work. add()/ remove() is where the trick lies

In my opinion, this is possible to resolve with Mo's Algorithm but C++ is not a good choice to implement an abstract solution. In some case, you need to use a big vector or Array to get store the frequency but in this case is possible to use a hash map. Unfortunately, the implementation of the C++ map is very bad. Maybe Java can be faster than C++ in this case.

Anyway, this is my solution, that uses pure Mo'a algorithm https://codeforces.com/contest/86/submission/103715846

After using ios_base::sync_with_stdio(false); it worked, lol!