Given an array A of size n. Do these q queries:
1 pos x: assign A[pos] = x;
2 l r k: find k-th smallest element in range [l,r]
Constraints:
n,q <= 1e5
A[i], x <= 1e9
My first aproach was to use a Wavelet tree with a BST(specifically a Treap) on each of its nodes. This gives a time complexity of O(n*log^2) and can do online queries(I still did it offline, i had to read all the input and compress the values because i don't want to make the Wavelet tree dynamic). However it has a really high constant factor and it takes 7-8 seconds to run with the full constraints.
Here's my code if you're interested (sorry if it's poorly written):
It is allowed to do queries offline, and the problem also has a tag of paralel binary search.
Can someone please show me the intended solution with paralel binary search (or even optimize my current code) ?
UPDATE: Solution founded :D https://robert1003.github.io/2020/02/05/parallel-binary-search.html#a-hrefhttpacmhdueducnshowproblemphppid5412hdu5412---crb-and-queriesa