P11570 「chaynOI R1 T3」镍铬合金机器人
题目背景
题目描述
给定一个长为 $n$ 的序列 $bot$。
有 $q$ 次询问，每次给出三个数 $l,x,y$，请你求出有多少个以 $l$ 为左端点的区间 $[l,r]$（$l\le r$）使得 $\text{mex}(\{bot_l,bot_{l+1},\cdots,bot_r\})\in[x,y]$。
注：一个可重集合 $S$ 的 $\text{mex}$ 函数 $\text{mex}(S)$ 指的是**最小**的没有在 $S$ 中出现过的**非负整数**，如 $\text{mex}(\{0,1,1,3\}) = 2$。
输入格式
无
输出格式
无
说明/提示
对于 $100\%$ 的数据，$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$。
**本题采用捆绑测试。**
+ Subtask 1(10pts)：$n,q\le 300$。
+ Subtask 2(15pts)：$n,q\le 2000$。
+ Subtask 3(15pts)：$bot_i \le 1$。
+ Subtask 4(20pts)：$x=y$。
+ Subtask 5(40pts)：无特殊限制。