A few days ago, I was solving a contest, where I found a problem, that I couldn't solve there.
You have got an array, size of N < = 105, and you are recieving up to M<=10^5 queries of the three types:
1 l r d -- increase every element at the segment [l;r] by t, i.e. X + = t
2 l r -- square root every element at the segment and round all of them down, X = [sqrt(X)]
3 l r -- get the sum at the segment
I tried several approaches, but none worked. If someone has some good idea, give me a clue.
p.s. messing around with the CF post editor :(
Edit: Sorry, forgot to mention: each X < = 105
