Editorial request for solving kquery problem from SPOj

general
, ,
1

Can anyone provide detailed editorial to solve KQUERY - K-query problem from SPOJ.

This problem has one editorial on codeforces I have already looked into it but found it very fast paced and didn’t understand that.

thanks in advance

2

Do it offlyn using segment,

Ans(i,j,k)=Ans1(i,k)-Ans1(j+1,k)

Where Ans1(i,k) denotes no.of elements greater than k in the suffix arr[i…n]

So indirectly we have to find values of Ans1(i,k),Ans1(j+1,k) for all queries ,

So for all queries sort them in decreasing order

For eg:
(3,4,2)

(2,5,3)

So we have tuples (3,2),(5,2),(2,3),(6,3)

After sorting (6,3),(5,2),(3,2),(2,3)

Now iterate array from n to i

Have a segment tree which could ans no.of elements in range,update segment as u traverse

Lets say u are at index i,u can now answer Ans1(i,k) for any k,as u have a seg for the suffix created ,just query for (k,inf) in segment

2 Likes
3

@vivek_1998299

can you also look into this one

https://discuss.codechef.com/questions/126033/can-you-answer-this-queries-problem-from-spoj

4

I just solved this problem.
If we apply simple brute force method then it will give time limit exceeding error.
So We can solve it in O(n.logn) via fenwick tree approach.
Steps to approch this problem:
Step1 - Take whole input and sort it w.r.t k-value(i,j,k) in decreasing order.
Step2- Then find answer for queries which are on top before updating the tree for same input values of k.