首先,据考生反应,这个题目并没有给数据范围,但是O(n2)的复杂度并过不去。那么我们就假设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。