P11901 数组的划分

本来这里应该有一段一脉相承的背景故事。但是因为福尔魔斯验题的时候写吐了，所以背景故事没了。

给出 $m$ 个数组 $s_1, s_2, \cdots s_m$ 和一个长为 $n$ 的数组 $t$。 定义 $f(l,r)$ 表示在所有 "把 $t_l...t_r$ 分成若干段，要求每一段都是 $s$ 中某个数组的子段" 的方式中，划分段数的最小值。 有以下操作： 1. 强制限定 $p,p+1$ 处必须划分，如果已经有了则取消。 2. 将 $t$ 的区间 $[l, r]$ 改成数组 $a$，会给出 $a$，每次的 $a$ 可能不一样。 3. 询问 $f(l,r)$，保证有解。 请你完成这些操作。

第一行四个数，$n,m,q,id$，表示 $t$ 的长度，总共有多少个文本数组 $s$，操作数，以及数据类型（参见说明）。 接下来 $m$ 行，每行先给出一个数 $k$，代表 $s_i$ 的长度，然后 $k$ 个数给出 $s_i$ 这个数组的元素。 下一行，给出 $n$ 个数，表示 $t$ 中的元素。 接下来 $q$ 行，每行表示一个操作，分别如下： 1. $1\ x$，表示若 $x,x+1$ 处不必须划分，则标为必须划分，否则取消。 2. $2\ l\ r\ a_1\ a_2 \cdots a_{r-l+1}$，表示令 $\forall l \le i \le r，t_i = a_{i-l+1}$。 3. $3\ l\ r$，表示询问 $f(l,r)$。

对于每次询问，输出一个数表示答案。每个答案占一行。

## 样例解释 对于第一组样例，初始数组为 $[2,3,3,2,1]$ ，段数最小分割的方式为 $[2,3|3,2|1]$ ，故输出 $3$ 。然后限制了 $3,4$ 之间必须分割，故最小的分割方式为 $[2,3|3|2|1]$ ，输出为 $4$ 。之后数组被修改为 $[2,1,3,2,1]$ ，段数最小的分割方式为 $[2|1|3|2|1]$ ，故输出 $5$ 。最后取消了 $3,4$ 之间必须分割的限制，最小分割方式为 $[2|1|3,2|1]$ ，输出 $4$ 。 ----- ## 数据范围 记 $\sum\limits_{i=1}^m |s_i|= M$ ，对于所有操作 2， $\sum\limits_{i=1}^t |r_i-l_i+1| = T$ ，其中 $t$ 是操作 2 的出现次数， $V$ 为数组中和修改后的数组中的元素的最大值，则各数据点的限制如下： | 测试点 | $n, M, q \leq$ | $T\leq$ | $V\leq$ | $id=$ | 特殊性质| | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1\sim3$ | $50$ | $10^5$ | $10^9$ | $1$ | 无 | | $4$ | $1000$ | $1000$ | $10^9$ | $2$ | 无 | | $5$ | $1000$ | $0$ | $4$ | $3$ | 保证没有操作 1, 2 | | $6\sim7$ | $1000$ | $0$ | $4$ | $4$ | 保证没有操作 2 | | $8\sim11$ | $1000$ | $1000$ | $4$| $5$ | 无 | | $12$ | $10^5$ | $10^5$ | $10^9$| $6$ | 无 | | $13\sim14$ | $10^5$ | $0$ | $4$| $7$ | 保证没有操作 1, 2 | | $15\sim17$ | $10^5$ | $0$ | $4$| $8$ | 保证没有操作 2 | | $18\sim25$ | $10^5$ | $10^5$ | $4$| $9$ | 无 | 对于所有数据，保证 $1\le n,M,q\le10^5, 0\le T\le 10^5,1\le V\le10^9, 1\le id\le9, l\le r$ 。$a,t$ 中的所有数都在 $s$ 中出现。 **保证给出的数组随机，但是询问的区间与询问的操作并不随机**。具体而言，初始给出的 $s,t$ 以及询问时可能给出的 $a$ 在符合上文所述限制之下的所有可能情况中等概率选取。而其他数据则不是随机的。