QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 6171. 序列区间段查询问题

Statistics

序列区间段查询问题:给出一个长度为 $n$ 的序列 $a$ 。$q$ 次询问,每次给定 $l,r,k$,求有多少个数对 $(l',r')$ 满足 $l \leq l' \leq r' \leq r$,使得 $\operatorname{mex}(\{a_{l'},a_{l'+1},...,a_{r'}\})=k$。

输入格式

输入的第一行包含两个整数 $n,q$。

接下来一行,包含 $n$ 个数,表示序列 $a$ 。

接下来 $q$ 行,每行三个整数 $l,r,k$。

输出格式

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

样例数据

样例输入

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\%$ 的数据,$n,q \leq 1\,000$。

对于 $100\%$ 的数据,$1 \leq n,q \leq 230\,000$,$0 \leq a_i, k \leq 10^9$。


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