Policy Based Persistent BIT

Правка en1, от hahavodox, 2017-10-08 00:47:02

Recently I come acroos a tecnique similar to Polyci 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 optimise 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 3SAT.

Теги 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)