I solved this problem with segment tree, but when I submitted my solution, it told me "Memory limit exceeded on test 4". I calculated my static memory usage, it's far from 512MiB. So why?
Just now, I tried changing my solution to be the same as official solution (linear memory usage), and I got MLE again...