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) ?
You can solve it using persistent segment tree
How would you handle the update queries? I can do it with persistent segment tree if there are no updates
Sorry I didn't notice.
Here’s a simpler way to tackle the problem:
Use a Segment Tree: Think of it like a big tree where each node covers a part of the array and keeps a sorted list of the numbers in that part.
For Updates: When you change a number in the array, you update the sorted lists in the parts of the tree that cover that number.
For Queries: To find the k-th smallest number in a range, you collect and merge the sorted lists from the relevant parts of the tree, then pick the k-th smallest from the merged list.
This method is pretty efficient and manages both updates and queries well.
I remember doing this for a similar problem without updates and small k constraint, but this problem has larger constraints for k, which is up to n. I can be mistaken but it seems your solution has a time complexity of O(n^2*log^2)
It's probably chatgpt solution
This approach is O(nq), since merging the lists take O(n).
How would you merge the lists to find the kth quickly?
Could you give the problem link?
let me know if you solve it ;)
https://marisaoj.com/problem/343
You can use segment tree or Fenwick tree where $$$t[i]$$$ is ordered_set of indices $$$j$$$ such that value $$$a[j]$$$ is in the $$$i$$$-th segment of segment/Fenwick tree.
I think that it is similar to my solution, but i used treaps instead of ordered sets. This is the first time I've heard about it and it seems pretty powerful. I wonder if it is allowed to be used in competitions, as it is pretty wild for a pre implemented data structure.
Tried the oredered_set out and it runs 1s slower than treap with full constraints :(
Use a merge sort tree and on each not use an ordered set for updates
That was also my first though but how are you getting kth smallest number in O(logn^2).