#PQJ1190x6171. QOJ 1190_6171
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。