### _Enigma__'s blog

By _Enigma__, history, 4 months ago,

Solution

Solution

Hint 1
Hint 2
Solution

Hint 1
Hint 2
Solution

Hint 1
Hint 2
Hint 3
Solution

### F. Triangles on Lattice

Solution

• +58

 » 4 months ago, # |   +20 I see many people (more than half AC submissions) passed E with $O(N\sqrt{N}logN)$ :(
 » 4 months ago, # |   +14
•  » » 4 months ago, # ^ |   +17 That is unfortunate. Even more so because I do have an AC on this one :( Luckily, the solution complexity is better here.
 » 4 months ago, # |   +35 I had a different $O(Q \sqrt{N})$ solution for The Antique Store. I noticed the need for point update and range sum data structure along with Mo's algorithm. But since Mo's can have $O(Q \sqrt{N})$ updates, a data structure supporting update in $O(\log{N})$ won't be enough.This suggests a need for a data structure which has faster updates but slightly slower queries. So, I used square root decomposition (on the array, not Mo's) for point update and range sum as updates are $O(1)$ and queries are $O(\sqrt{N})$. Since there are only $O(Q)$ queries, overall complexity is $O(Q \sqrt{N})$.Code