Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя patience

Автор patience, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Where is the original problem from?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.