Hello friends! I have tried to solve the 343D problem using a Segment Tree. When I submitted with the upper limit on the arrays of 4*MAX, it ended up with WA Test 10. Somehow, I was able to "fix" the code by changing the upper limit on the array to be 8*MAX instead of 4*MAX. Can anyone explain why this would result in a different answer (and why there is no index out of range (or some RE) when using 4*MAX)? Thanks for your help!
Submission for 4*MAX (WA): http://mirror.codeforces.com/contest/343/submission/19451573
Submission for 8*MAX (AC): http://mirror.codeforces.com/contest/343/submission/19451700
When the size of your array is n, then you can define the size of segment tree as n × 4. But if the size of your array is n × 2, then the size of the segment tree must be n × 8 ((n × 2) × 4).
You can read more here about accessing index out of range in C++.