#PQJ1190x6171. QOJ 1190_6171

    ID: 2563 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2020线段树分块

QOJ 1190_6171

序列区间段查询问题:给出一个长度为 𝑛 的序列 𝑎 。 𝑞 次询问,每次给定 𝑙 , 𝑟 , 𝑘 ,求有多少个数对 ( 𝑙 ′ , 𝑟 ′ ) 满足 𝑙 ≤ 𝑙 ′ ≤ 𝑟 ′ ≤ 𝑟 ,使得 mex ⁡ ( { 𝑎 𝑙 ′ , 𝑎 𝑙 ′ + 1 , . . . , 𝑎 𝑟 ′ } )

𝑘 。

输入格式

输入的第一行包含两个整数 𝑛 , 𝑞 。

接下来一行,包含 𝑛 个数,表示序列 𝑎 。

接下来 𝑞 行,每行三个整数 𝑙 , 𝑟 , 𝑘 。

输出格式

对于每组询问,输出一行一个整数,表示答案。

样例数据 样例输入 10 10 0 0 4 1 1 3 0 4 6 1 2 2 1 4 10 2 1 4 0 4 8 0 4 4 1 1 6 0 5 8 0 2 10 3 3 9 6 1 4 0 样例输出 1 10 3 7 0 10 4 0 0 3 子任务

对于 10 % 的数据, 𝑛 , 𝑞 ≤ 1 000 。

对于 100 % 的数据, 1 ≤ 𝑛 , 𝑞 ≤ 230 000 , 0 ≤ 𝑎 𝑖 , 𝑘 ≤ 10 9 。

注 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。