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.net/contest/869/problem/E
This can be solved with this trick easily combining this with Baby Step Giant Sweep line along with persistent KSAT.
.
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.
not sure if you actually didn't got the
trolltechnique right or just contributing to 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...
bitset = troll
Blogs like these are why I still browse codeforces.
Auto comment: topic has been updated by hahavodox (previous revision, new revision, compare).