Sanjit-OP's blog

By Sanjit-OP, history, 22 months ago, In English

Hi, code forces, I have been getting haunted by this problem for a long time now.

Would you please help me to understand what data structure and approach are needed to solve this problem? This problem is not from any live contest.

Given an array A having N integers in the range [-1e8, 1e8] and Q queries each having 3 integers [L, R, K]. For each query, the task is to return the sum of K's smallest elements in the subarray A[L...R] where K = [1, R-L+1].

My approach:

  1. Build a merge-sort segment tree and a prefix-sum segment tree.

  2. For each query do a binary search over an integer (say V).

  3. Now count the elements in the merge-sort seg tree with values <= V and also return the prefix sum of such elements.

  4. Return a pair from step-3 {prefix_sum, C}, where prefix_sum denotes the sum of chosen elements and C denotes the count of chosen elements over binary-search value V.

  5. If C < K then search for higher value V in binary search. Otherwise, the current answer sum of K's smallest element = prefix_sum + (C-K)*V (this also handles duplicates during upper_bound search in each node).

Time complexity: Q.log(X).log(N).log(N), where X is 1e15.

  • Q = Total queries

  • log(X) = Binary search over max answer limit.

  • log(N) = Iterating over segment tree nodes

  • log(N) = Upper_bound on prefix sum on each node.

Thanks in advance :)

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By Sanjit-OP, history, 4 years ago, In English

Hello codeforces! I wish to prepare for the upcoming ICPC 2021, but as per the current situation of global pandemic(COVID-19), I don’t know whether it will be possible for the community to host ICPC next year or not. If someone has any information regarding please share! Help appreciated! Stay safe! Thank you.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it