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.↵
↵
↵
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.↵
