Description

You are given two permutations $a$ and $b$, both consisting of $n$ elements. Permutation of $n$ elements is such a integer sequence that each value from $1$ to $n$ appears exactly once in it.

You are asked to perform two types of queries with them:

  • $1 \ l_a \ r_a \ l_b \ r_b$ — calculate the number of values which appear in both segment $[l_a,r_a]$ of positions in permutation $a$ and segment $[l_b,r_b]$ of positions in permutation $b$;
  • $2 \ x \ y$ — swap values on positions $x$ and $y$ in permutation $b$.

Print the answer for each query of the first type.

It is guaranteed that there will be at least one query of the first type in the input.

Idea

看到这道题我第一个想法就是:带修改主席树。

令 $p_i$ 代表 $a_i$ 在 $b$ 中出现的位置,每次询问就是求区间 $[l_a,r_a]$ 中,权值在 $[l_b,r_b]$ 之间的数字个数,修改就是简单的单点修改。

静态主席树的写法大家非常清楚,我把它理解为前缀权值线段树。如何动态维护一个前缀数组呢?采用树状数组即可。我写的带修改主席树本质就是树状数组套主席树,树状数组上每个节点对应储存了相应区间信息的主席树。

这样写实测过不了。原因很简单,空间不够。但是这个东西还是很有用的(我写的也很好看),代码放在文章末尾了。

如何在 Codeforces 上通过此题?把主席树换成 $\text{pbds}$ 里的 红黑树 即可。

Code

以下是在 Codeforces 上可以通过的代码。

以下是带修改主席树,在极限数据下爆空间了。