### Llarc's blog

By Llarc, 9 days ago,

I'm sorry to bother this community, but there are a lot of interesting tricks involved and I'm enjoying it so much that I'm posting it to share with you.

We first try to solve a weakened version of this problem, that is, $1≤a_i≤2$, which can be helpful to think about. For this problem just enumerate $k$ and maintain that information: the number of $1$'s and $2$'s on the left and right of $k$, and the number of $(x,y)$ binary groups satisfying $a_x=1$ and $a_y=2$ or $a_x=2$ and $a_y=1$ on the left of $k$.

This can then be computed within $O(n)$, here is the code for this part : https://codeforces.cc/contest/1400/submission/167092044

We assume a number $b$ to represent the threshold of the classification discussion. When the number of a number exceeds $b$, it means that it is sufficiently large to be given separate attention. It is easy to derive that there are at most $n/b$ different such numbers.

If $a_i$ and $a_j$ are both such numbers, then we can simply extract them two by two and use the $O(n)$ algorithm above to compute them with a total complexity of $O(n^2/b)$.

If $a_i$ or $a_j$ are not such numbers, then the computation is tricky because their distribution is messy, but it is easy to know that the number of binary groups $(x,y)$ that satisfy $a_x=a_y$ and the number of $a_x$ is less than $b$ is no higher than $nb$.

So we preprocess all such binary groups and subsequently use Mo's algo optimization on them, which can be computed easily $O(1)$ moving the pointer and taking $O(nb^2+n^2/b)$ for the computation.

We just need to take $b=n^{0.3}$, then the total complexity is $O(n^{1.7})$, end.

I found it almost impossible for me to avoid Mo's algo when optimizing, if anyone finds something faster than n^(5/3), or the same time and without Mo's algo, please contact me. Thanks in advance.

• +56

 » 9 days ago, # |   +7 This problem can be improved to $O(n\sqrt{n\log n})$ also using Mo's algorithm, I think this performs better than the $O(n^{1.7})$ one when $n\le 10^5$.
•  » » 9 days ago, # ^ |   +8 Any detailed description?