2998. 树链剖分主席树 2.0

【问题描述】

 炮姐提示:本题和1.0版本的区别是查询方式不一样,数据范围不一样!

在遥远的东方,有一颗斯坦纳树,笔直笔直的,没有一点分叉与树枝,直插云霄,高度为n,树上只有一种生物,啄木鸟,没错就是啄木鸟,所以这个树上有很多啄木鸟洞,但是作为一个通天的斯坦纳树,树上有不同品种的啄木鸟(反正就是成千上万种),现在我们对啄木鸟编号(反正就是编号),保证编号是非负整数,保证编号在1e5以内,现在炮姐有q次查询,每次想知道待查询的编号品种的啄木鸟在这棵树的一个区间[L,R]上有多少只。
【输入形式】

第一行一个整数n,表示斯坦纳树上有n只啄木鸟,接下来一行有n个数,表示每只啄木鸟的编号。(树的坐标是1~n,所以不会有啄木鸟在1.5这样的位置上,每个整数都有一只)。下面一行输入一个q,表示查询组数,接下来有q行,每行有三个整数L,R,x,表示炮姐想查询编号为x的啄木鸟在区间[L,R]上有多少只,0 < L,R,x,n,q <= 1e5。

【输出形式】

对于每个查询,输出一行表示斯坦纳树上的区间[L,R]上有多少只这种编号的啄木鸟。

【样例输入】

5

1 2 3 4 2

2

1 2 2

1 5 2


【样例输出】

1

2


难度等级: 0
总通过次数: 2
总提交次数: 78