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

3

@vivek_1998299

can you also look into this one