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

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

I tried this problem with segment tree first and got TLE. Then I used square-root but again got TLE. To solve the problem with square-root i used tree which size is sqrt(n) * sqrt(n), where n is the size of the array. In every block of the tree I kept sqrt(n) elements of the array sorted in ascending order. When update occur I push the element in a block where it's index remain and again sort this block. And when i got query operation for every block which is in the range I found how many elements are less than the given value. This can be done with binary search for every block. Please tell me where i should optimize my code. Here you can have a look at my code .

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

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

Cant u just use some BIT instead of resorting block everytime?(i mean, to update with O(log(n)) instead of O(sqrt(n)*log(n)))

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

    Then we should compress the value of the array. Isn't it???

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

    I am having problem with it too. First, i used BIT which made complexity of per update log(n) and per query sqrt(n)*log(n) + sqrt(n). But i got TLE. I don't know why! Then, i used 2D BIT and update became log(n)*log(n) and query log(n)*log(n) + sqrt(n). But still getting TLE. Please help me. Here is my Code . Thanks in advance.

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

UPD: Problem Solved :)