QQ线段树模板

QQ发明了一种线段树  

众所周知, 线段树可以在nlogn的时间复杂度内进行查询以及插入.

定义一个名词:相似数组.   

我们定义两个数组满足以下条件为相似数组:

    1.长度相同

    2.都是严格递增的

    3.他们只有一个位置是不同的,并且其他不变的位置相对位置不变

现给定一个严格递增的数组a, 进行q次操作,每次操作有一组询问:

有多少个数组b和数组[a_{l ,}a_{l + 1} , ........ a_{r - 1,} a_r]是相似数组, 并且相似数组b中最大值不大于k

tip：对于第三条，举个例子[1, 2, 4, 9] 是 [1, 2, 4, 5]相似数组，但和[1, 2, 3, 4]不是，因为4的相对位置从3变到4

第一行包括三个数字: n, q, k 分别代表 数组a的长度, 询问次数, 以及题目条件中的k

第二行有n个数字, a1,a2,…,an(1≤ai≤k).

接下来q行, 代表q次询问, 输入每次询问的 l, r

1 <= n, q <= 1e5, 1 <= k <= 1e9

输出q行,每行询问对应的答案

4 2 5
1 2 4 5
2 3
3 4

4
3

tip: 第一次询问满足条件的相似数组有[1,4],[3,4],[2,3],[2,5]