Given an array of length $$$n$$$ of positive integers $$$a_1, a_2, \dots a_n$$$ and $$$q$$$ queries. Each query has $$$4$$$ integers $$$l, r, s, e$$$.
Let's say array is $$$[1, 2, 2, 3, 3, 3, 6]$$$, and query with $$$l = 1, r = 6, s = 1, e = 3$$$. The answer is "YES" if the subarray $$$[l, r]$$$ has numbers with a frequency equal to $$$1$$$, $$$2$$$, and $$$3$$$. i.e. has frequency $$$s, s + 1, s + 2, \dots e$$$. How to answer the queries fast?
Constraints $$$(1 \leq n \leq 10^5)$$$ $$$(1 \leq a_i \leq 10^6)$$$ $$$(1 \leq q \leq 10^5)$$$ $$$(1 \leq l \leq r \leq n)$$$, $$$(1 \leq s \leq e \leq n)$$$.
Examples
5
1 2 3 2 4
3
2 4 1 2
1 4 2 2
2 3 1 4
Answer
YES
YES
NO
where's this problem come from? i wanna know :]
We can solve this in O((n + q) * sqrt) ig
Using MO's we can process the queries offline, maintaining two arrays, freq[v] & cnt[u];
Freq[v] is the frequency of value v, cnt[u] is the count of frequencies equal to u
we can maintain these 2 arrays during the MO's
Now when the the L and R pointers are pointing at a query which needs to be answered, we can simply iterate on the range [s, e] and check cnt[i] : s <= i <= e This doesn't cost much because the range [s, e] won't be be longer than sqrt :)