theretardprogrammer's blog

By theretardprogrammer, history, 15 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it