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.