hahavodox's blog

Policy Based Persistent BIT
By hahavodox, history, 7 years ago, In English

Recently I came across a technique similar to Policy based DS, a Policy Based Persistent BIT. To basic idea is to keep the BIT balanced by HLD. Naive algo is O(n^2). But you have to optimize using bitset to make it O(nlog n). You can perform dynamic range update range query and orthogonal range minimum IDA* search easily in O(Nlog N).

Example:http://mirror.codeforces.com/contest/869/problem/E

This can be solved with this trick easily combining this with Baby Step Giant Sweep line along with persistent KSAT.

  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

It'd be helpful if you posted an implementation. Also, what is range minimum ida* search. Google tells me it's iterative deepening, but it's unclear how that applies here.

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

    not sure if you actually didn't got the troll technique right or just contributing to it.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Can't say I realized it was a troll. The IDA* search part and KSAT were strange, but nothing else really made it clear to me that they were trolling...

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

Blogs like these are why I still browse codeforces.

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

Auto comment: topic has been updated by hahavodox (previous revision, new revision, compare).

→ Reply