Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

eftikhar_azim's blog

By eftikhar_azim, history, 9 months ago, In English,

This code of Light Oj 1080 gets TLE, I can't understand the reason behind this. My idea is to go to the leaf node of the tree in the range and flip the bit. What should be the best idea to solve this problem ?

 
 
 
 

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is expected to time out since updating a single node take log(N) time but in the worst case you maybe asked to update entire ranges thereby making the complexity QNlog(N).

Try looking up for range updates with point queries. This is a good starting point. You can use a segment tree or a fenwick tree to implement this question. After this you can learn about the general case of range updates with range queries.

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

    Also, you can check here too. It was very helpfull when I was learning Lazy Propagation.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amusingly,it can be solved using sqrt decomposition with bit masking. Here's my implementation: Link