Policy Based Persistent BIT

Правка en4, от hahavodox, 2018-12-29 12:30:00

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://codeforces.me/contest/869/problem/E

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

Теги hld, bit, persistence, ds, monopoly, koto kichu pari, safety pin, bitset

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский hahavodox 2018-12-29 12:30:00 4
en3 Английский hahavodox 2018-12-18 21:35:18 0 (published)
en2 Английский hahavodox 2017-10-08 01:00:08 16 (saved to drafts)
en1 Английский hahavodox 2017-10-08 00:47:02 543 Initial revision (published)