How to answer the queries fast?

Правка en2, от theretardprogrammer, 2023-08-09 04:23:17

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский theretardprogrammer 2023-08-09 04:23:17 0 (published)
en1 Английский theretardprogrammer 2023-08-09 01:28:27 713 Initial revision (saved to drafts)