Inititaly we have n(1<=n<=10^5) numbers . There are two operations..
1.a L R : Add 1 to each number having indices between L and R
2.q L R : Query for the number of numbers(perfect cube) between indexes L and R.A perfect cube is a number which is cube of an integer.So 1,8,27 perfect cube,but 3,9,20 are not perfect cube.
sample input:
n=8,q=6
3 6 2 8 26 1 125 9
q 2 8
q 4 4
a 2 7
q 4 6
a 1 8
q 1 8
output: 3 1 1 1
how can i solve this problem using segment tree? thanks in advance.
Where is the original problem from?
it is our inter university programming contest problem.. it is not upload yet any site
Keep in the nodes of the segment tree:
For the increment operation, all numbers that were cubes are not cubes anymore, so zero the first count. The distance decreases by 1: if it becomes zero, find the number(s) that became a cube by following the zeros in the tree, mark them as cubes and set their distance to the next cube.