Help me with this data structure problem pls!

Revision en1, by PUSSY_LICKING_LOLI_69, 2024-09-08 12:28:56

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):

My Code

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) ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PUSSY_LICKING_LOLI_69 2024-09-09 03:15:27 171
en1 English PUSSY_LICKING_LOLI_69 2024-09-08 12:28:56 5993 Initial revision (published)