DeWitt's blog

By DeWitt, 4 years ago, translation, In English

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

Read more »

  • Vote: I like it
  • +30
  • Vote: I do not like it