P4867 Gty's Girl Sequence

Autumn and Bakser are studying Gty's girl sequence again, but they have run into a difficult problem. Given a segment of girls, they want you to help compute the number of distinct beauty values whose beauty is in $\in [a,b]$ within this segment. For convenience, we assume all beauty values are within $[1,n]$. Given a positive integer sequence $s$ of length $n(1 \le n \le 10^5)$ with $s_i(1 \le s_i \le n)$, and $m(1 \le m \le 10^6)$ queries $l,r,a,b$, for each query output, in $s_l \cdots s_r$, the number of distinct values that are $\in [a,b]$.

The first line contains two integers $n,m(1 \le n \le 100000,1 \le m \le 1000000)$, representing the number of elements in sequence $s$ and the number of queries. The second line contains $n$ integers $s_1 \cdots s_n(1 \le s_i \le n)$. The next $m$ lines each contain $4$ integers $l,r,a,b(1 \le l \le r \le n,1 \le a \le b \le n)$, with the meaning as described in the statement. It is guaranteed that all numbers involved fit in C++ int. The input is guaranteed to be valid.

For each query, output a single line representing, in $s_l \cdots s_r$, the number of distinct values that are $\in [a,b]$.

【Partial explanation of the sample】 `5 9 1 2` The subsequence is `4 1 5 1 2`. The values within $[1,2]$ are 1, 1, 2. There are 2 distinct values, so the answer is 2. `3 4 7 9` The subsequence is `5 1`. The values within $[7,9]$ are 5. There is 1 distinct value, so the answer is 1. `4 4 2 5` The subsequence is `1`. There are no values within $[2,5]$, so the answer is 0. `2 3 4 7` The subsequence is `4 5`. The values within $[4,7]$ are 4, 5. There are 2 distinct values, so the answer is 2. It is recommended to use input/output optimization. Translated by ChatGPT 5