思路:区间容斥计算

数据范围？

首先，据考生反应，这个题目并没有给数据范围，但是$O(n^2)$的复杂度并过不去。那么我们就假设n , q <= 100000。

区间差分？

考虑这种区间问题一般都能用前缀和或者差分来解决。回忆求区间和，我们可以用前缀和 + 差分的方式来解决。

那么这种区间计数的问题，我们可以用前缀和 + 差分的方式来解决吗？

题目描述

米小游有一个长度为$n$的数组$a$，她会询问$q$次，每次会问你区间$[l,r]$中有多少个连续子数组包含$x$。

如果数组$a$可以通过从数组$b$的开头删除若干(可能为零或全部)无素以及从结尾删除若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子数组。

输入描述

第一行输入一个整数 $n$ 表示数组长度。

第二行输入 $n$ 个整数 表示数组。

第三行输入一个整数 $q$ 表示询问次数。

接下来 $q$ 行，每行输入三个整数 $l,r,x$ 表示一次询问。

输出描述

对于每一个询问，在一行上输出一个整数，代表答案。

3 
1 2 1000
3
1 2 1
1 3 1
1 3 40

2
3
0

说明

对于第一次询问，子数组 $[1, 1]$ 和 $[1, 2]$ 包含1。