2996. 树链剖分主席树

【问题描述】

众所周知,主席树是非常强大的数据结构,又称可持久化线段树,可以解决非常多的普通线段树解决不了的区间问题,树链剖分也是非常常见的数据结构,当然这不重要,反正炮姐都不会。但是炮姐也有梦想啊,所以炮姐打开了CG程序设计基础OJ去找题,总算是找到了一道单点查询的题,让我们来看一看吧。

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

第一行一个整数n,表示斯坦纳树上有n只啄木鸟,接下来一行有n个数,表示每只啄木鸟的编号,每只啄木鸟都在整数坐标上(树的坐标是1~n,所以不会有啄木鸟在1.5这样的位置上,每个整数都有一只)。下面一行输入一个q,表示查询组数,接下来有q行,每行一个整数,表示炮姐想查询的啄木鸟品种编号,数据保证0<n<1e6,0<编号<1e8。
【输出形式】

对于每个查询,输出一行表示斯坦纳树上有多少只这种编号的啄木鸟。
【样例输入】

5

1 2 3 4 2

2

1

2


【样例输出】

1

2


note:数据很强,放心食用。

难度等级: 0
总通过次数: 36
总提交次数: 369