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)
showing 5 of 11
show all

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