patience's blog

Advanced segment tree problem
By patience, history, 9 years ago, In English

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.

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

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where is the original problem from?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is our inter university programming contest problem.. it is not upload yet any site

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Keep in the nodes of the segment tree:

  • how many of the integers in the interval are perfect cubes
  • the smallest distance between a[i] and the smallest cube bigger than a[i].

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.

→ Reply