i need a good solution to this problem… the editorial in hackerearth wasn’t good for me…
the question link is below…
please provide a good explanation of concept… i really need to know how to solve these type of questions…in which there are very large queries…
what i thought was of using unoredered map but that gave me TLE…
PLEASE HELP ASAP…
THANK YOU
I solved using MO’s algorithm and I think test cases were weak because my solu will get a TLE in strong test case.
I am too looking for an explanation using Segment tree or BIT or any other technique.
I can see a lazy segment tree approach. First input the data, and store all the numbers in a vector<vector<int>> occurrence;, such that occurrence[i][j] gives the index of the jth occurrence of i.
Make a lazy segment tree with all values 0, that allows range addition/subtraction updates and element queries. If the value in the segment tree is not 0, then it’s not a happy segment. The value represents how many values in m don’t like this r.
Then for each value i in m add 1 to the range from the 1st occurrence of i to just before the h_ith value, and from the h_i+1th value to the end. These are the ranges you are not allowed because i won’t have a correct value. sort the queries by l. For every query, if you have to move l forward, undo the last change we made with the value at l, and do the same update. Lets say that update was from ath occurrence to the bth occurrence, and from the cth occurrence to n, then our new update will be from a+1th occurrence to the b+1th occurrence and the c+1th occurrence to n. To check whether it’s a happy segment, just check the element at the index r.
I too tried with Mo’s but got TLE(only 9 points), I used a single pointer to check the number of numbers having frequency not equal to the required frequency. Where should I optimize my code still? Link to my solution Link .