BGQRS - Unofficial Editorial

there is no need for a boolean(type2, in you code) to tell us whether reset is necessary or not. Notice you can simply set tree[node].st = -1 (for example) to indicate this node doesn’t require reset operation. Our solution are two much similar… hope we don’t find ourself in plagiarism :stuck_out_tongue: (LOL). couldn’t find the bug Yet.

And Why did you choose KMax as 20?

@vishveshcoder As you can see, I set K (the initial size of a block) to be max(20, sqrt(n)). The constant 20 is chosen arbitrary. I did it in order to avoid extremely small blocks when sqrt(n) is small. Notice that later I set num_of_blocks = N / K. However, I think that you can just write K = sqrt(n) and everything should work just fine.

As your solution is too lengthy I can not read it completely but the thing is that your propagation of updates is not correct , for the test case-


7 6

1 2 3 4 5 6 7

1 2 6 5

2 2 7 1

1 2 5 2

3 1 4

3 3 7

3 2 6

your codes output is “6” but it should be “2” so simulate your codes
working on this test case and you will know the mistake.