cf323c

比较水的一个题。

主要是考虑这个排列的性质。

如果只考虑一次询问，让你把在 \(a:[l_1,r_1]\) 里的与 \(b:[l_2,r_2]\) 的相同数的个数求出来。

我们有这样一种思路，把 \(a_x\) 一个一个加进去，直到 \(x=l_1-1\)。 记录当前状态，然后接着加入，直到 \(x=r\) ，记录状态。

把这两个状态分别求出在 \(b:[l_2,r_2]\) 里面有多少个。在相减，便是所求。

线段树维护即可，设 \(p_i\) 表示 \(i\) 在 \(b\) 中的位置。那么加入 \(a_x\) 操作等价于在 \(b\) 的 \({p_{a_x}}\) 处加 \(1\) ，然后区间求和。

那么多次询问用主席树记录状态即可。

代码不放了。