You should use a SQRT-decomposition. Let BLOCK = sqrt(N) In kth element of the decomposition you should store hash_set containing numbers from k * BLOCK to (k + 1) * BLOCK.

i am getting time limit on test 13 , with sqrt-decomposition.

You can solve this task using binary search.
Sort all numbers with their indexes.
Now if we get query L R X, we use binary search to find all X numbers between
our numbers. If we found X in binary search, check it's index, if it's >= l and <=r then
answer for query is 1. If such number wasn't found in binary search, answer for query is 0.

> if it's >= l and <=r then answer for query is 1

it isn't enough 'cause you can have several cities with the same population and simple binary search finds just one of them

3
666 666 666
1
1 1 666

has to answer 1