Advanced segment tree problem

Revision en2, by patience, 2015-09-16 20:14:30

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.

Tags datastructure, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English patience 2015-09-16 20:14:30 60
en1 English patience 2015-09-16 20:13:14 536 Initial revision (published)