After reading the solution to problem D from last CF round, I decided to implement it(the idea with 2D segment tree). I know that there are other(faster) ways to implement segment tree as needed for RMQ, but I wanted to implement it with standard(check my code for what I call standard) implementation of 2D seg tree. Unfortunately, I got TL on test 16. So I wanted to ask whether there is some way to optimise my solution(without using the other faster way to implement segment tree). Link to my code: http://mirror.codeforces.com/contest/677/submission/18295468
This is actually not a 2D segment tree. This is a quad tree which has worst case complexity O(N) per query (in your case it can become O(N*M) per operation). Try implementing it using a 2D Fenwick tree or like you said 2D segment tree (not Quad tree).
Do you have a link to a good implementation of real 2d segment tree? I couldn't find it on google(at least none were god enough)?
This is the best implementation I've seen. It's clean and easy to read.
this might help you
just translate the page to English