So, Just few hours back I learned that complexity of lower_bound(st.begin(),st.end(),val) is much much higher than st.lower_bound(val). where st is normal stl set in c++

As you can see the only difference between 81895138 and this 81894342 is the one mentioned above.

I thought I should share it with the community as me myself and my few friends didn't know about this.

I don't know the reasons for this, it would be really helpful if someone could give the reasons and actual complexity of lower_bound(st.begin(),st.end(),val).

We are given A array with N elements and Q queries are done on it. In each query, a range (L,R) and a no. K is given and we have to find no of element with frequency >=K in that range.

constraints A[i]<=1e6

N<=1e5

Q<=1e5

I am trying to do it using MO algorithm. Kepping an array to store frequency of each element. But how do i find elements with frequency >= k without transversing (otherwise complexity will be much higher)

Thanks in advance