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

Spoj Problem ANDROUND
Автор starbot, история, 7 лет назад, По-английски

Hello !!!

I was wondering about how can we solve this problem using BIT.

I got AC using seg tree but I also saw a comment where someone solved it using BIT.

Help would be appreciated.

Thanks.

Problem :- http://www.spoj.com/problems/ANDROUND/

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

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

Can you tell me your seg tree approach? I was only able to think of a O(n * 32) with 2 pointers.

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

    Well its a very basic seg tree problem. (nlogn)

    First you need to know that each a[i] will be equal to combined AND (&) of i+k and i-k elements. So all you need to do is build a seg tree in which each node contains AND of the range under it. Then for each array element you need to perform a query from i to i+k and i to i-k and print the ans. Since the array is cyclic you need to see that you don't go over n or below 0. That's it. Its complexity is nlogn.

    Here's my code :- https://pastebin.com/7S9Ez45F

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There exists a range-update range-query method for fenwick tree: see this

Now fenwick tree becomes exactly like segment tree for this problem.

Edit: My bad. I realised that cumulative bitwise AND of a range cannot be negated like range sum and xor.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

You can make 32 rsq bit's trees for each bit to get the and of the range.

→ Ответить