Given an array of 'N' integers, I need to perform two kinds of queries :
There are 'Q' queries. This question was in a Hiring challenge on Hackerearth (Challenge is over now) so I can't provide a link to the statement. I want to know if this problem can be solved with complexity better than Q*Log^2N asked 07 Jan, 23:57

I did it using merge sort tree but it's as expensive as your's solution. Did you solve the last combinatorics question? answered 08 Jan, 03:48
I used a set and map for duplicates in every node of a segment tree. Got TLE. Yeah, I solved the last question.
(08 Jan, 11:59)
@hemanth_1 can you please explain your approach you applied to the last question? The stars and bars method was not working for me.
(08 Jan, 17:48)
Let dp[i][j] be the number of ways to take 'j' items in the first 'i' boxes. Since the limit for each box is 'A' for the first 'P' boxes, if i <= P, then: dp[i][j] = dp[i1][j]+dp[i1][j1]+....+dp[i1][jA], because you can take 0 to 'A' items from the ith box, and the rest must come from the previous ones. For i>P you can take the summation based on 'B'. I calculated this upto 1000 items. Now, you need to count number of ways to get sum >= X, so I calculated all possible ways and subtracted the number of ways to get sum <X using the dp table. There will be (A+1)^P * (B+1)^Q different ways.
(09 Jan, 16:19)
So, the answer for a given value 'X' will be (A+1)^P * (B+1)^Q  (dp[n][0]+dp[n][1]+...+dp[n][x1])
(09 Jan, 16:22)
Did you get 100pts for the query problem ?
(09 Jan, 16:23)
@hemanth_1 80, TLE in 4 test cases.
(09 Jan, 17:36)
@hemanth_1 how much did you score out of 400? Did you receive any notifications of the interview?
(10 Jan, 15:55)
I scored 350 (lost 50 in query problem), I got a mail today saying that I got shortlisted
(10 Jan, 21:09)
@hemanth_1 Yep, I also received an email yesterday from hackerearth.Did the cogoport team call you after that?
(11 Jan, 19:15)
@assassin28 No.
(11 Jan, 22:32)
@hemanth_1 did they call you?
(21 Jan, 03:11)
@assassin28 no
(21 Jan, 23:45)
showing 5 of 13
show all

Answer is hidden as author is suspended. Click here to view.
answered 10 Jan, 11:41

@hemanth_1 did you use merge sort tree? answered 22 Jan, 01:01
I used a segment tree, with a set and a map in every node
(22 Jan, 14:14)
How did you find answer to second query using this?
(22 Jan, 15:41)
You need to find the smallest number > P in [L,R]. Since there is a set in every node of the segment tree, you can use upper_bound to find the smallest number > P in the range for that node. Since every query will visit at most O(logN) nodes, you only need to do this those many times. Finally, you will return the minimum of all upper_bounds that you found in all the nodes that you checked.
(24 Jan, 21:29)

https://discuss.codechef.com/questions/120954/minimumnumberquery/120958
Thanks, but I think that has the same complexity as my solution.