So I wanted to see if it was possible to solve this problem [160-E](https://codeforces.me/contest/160/problem/E) with a sparse segment tree 2D. I made this implementation (because I didn't find any) [submission:386015499]. Unfortunately, it passes in approx 1200 ms and 80 MB (the best it did was 1031 ms with iterative queries). ↵
↵
Anyways, I'm sharing the implementation [submission:386021321] (slower but more general) in case anyone finds it useful, it allows queries and point updates in $O(log^2 n)$ with the preprocessing of all the intervals in $O(n \ log \ n)$. It is possible to make some optimizations but it should pass under 2 seconds. ↵
↵
UPD: I managed to get AC with some optimizations [submission:386153449] :)
↵
Anyways, I'm sharing the implementation [submission:386021321] (slower but more general) in case anyone finds it useful, it allows queries and point updates in $O(log^2 n)$ with the preprocessing of all the intervals in $O(n \ log \ n)$. It is possible to make some optimizations but it should pass under 2 seconds. ↵
↵
UPD: I managed to get AC with some optimizations [submission:386153449] :)
