I did this problem in a different way. I used two segment trees with lazy propagation on both of them. My solution passed in 0.30 secs.
segment tree for queries - segQ
segment tree for array - segA
First, I updated segQ with a val=1 (as every operation will be executed at least once). Then I ran a loop from m-1 to 0 and updated all the queries of type 2. Like for example for the 3rd sample test case of the problem, if the query was 2 1 5, then first I got the initial value on that node by doing query on segQ to get the no. of times this operation will be executed (say x) in future then with that value I updated the operations from 1 to 5 (i.e. l and r of the query) which means operations from 1 to 5 will be called x more times so add.
Then after that I ran a second loop from 0 to m-1 but this time for queries of type 1 and updated segA with the values for that particular command on my segQ.
This is my full code
If for commands we build the difference sequence in backward order, as the editorial does, but for the array we build it in forward order, then it is sufficient to just keep the running totals (without actually restoring the corresponding sum sequences).
Finally was able to solve this after learning from the editorial about difference array. Here is my solution: [Yay! AC <3][1]
[1]: CodeChef: Practical coding for everyone
For each command, we need to count how many times it’s executed during the whole process, denoted by cnt[i]. We can iterate the commands backwards, and every time we meet a command 2 l r which is executed k times, we add k to cnt[l∼r]. When we know cnt[i] for every command i of type 1, we can easily figure out the answer by maintaining the difference array of a.
Can anyone explain this.I am completely unable to understand.
lazy propagation is an overkill here actually. Normal segtree would work. I used a segtree but now am realising that there was an even easier way using a difference array.
Because the alternative is to update the actual array, which will result in O (N) complexity per command, thus O (N^2) comolexity for whole task, giving TLE.
using difference array, u apply update in constant time.
I have used difference arrays only and got 100 points. I have added explanation just above, alongwith a link to my code.