P11570 "chaynOI R1 T3" Nickel-Chromium Alloy Robot


You are given a sequence $bot$ of length $n$. There are $q$ queries. Each query gives three numbers $l, x, y$. For each query, find how many intervals $[l, r]$ (with $l \le r$) starting at $l$ satisfy $\text{mex}(\{bot_l, bot_{l+1}, \cdots, bot_r\}) \in [x, y]$. Note: For a multiset $S$, the $\text{mex}$ function $\text{mex}(S)$ is defined as the **smallest** **non-negative integer** that does not appear in $S$. For example, $\text{mex}(\{0,1,1,3\}) = 2$.

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries. The second line contains $n$ numbers, representing the sequence $bot$. The next $q$ lines each contain three integers $l, x, y$.

Output $q$ lines in total. Each line contains one integer, representing the answer.

For $100\%$ of the data, $1 \le n, q \le 3 \times 10^5$, $0 \le bot_i < n$, $0 \le x \le y \le n$, $1 \le l \le n$. **This problem uses bundled testdata.** + Subtask 1 (10 pts): $n, q \le 300$. + Subtask 2 (15 pts): $n, q \le 2000$. + Subtask 3 (15 pts): $bot_i \le 1$. + Subtask 4 (20 pts): $x = y$. + Subtask 5 (40 pts): No special constraints. Translated by ChatGPT 5