501000047 - Karry5307

您正在学习如何 像 \texttt{K\color{red}arry5307} 一样ssh AK所有比赛，所以您来做这道数据结构题：

维护一个长为 n 的序列 a，有 m 次操作。

  1. 将区间 [l,r] 的值修改为 x。

  2. 令集合 p={a_i | l \le i \le r} ，询问集合 p 内的元素个数。

输入

第一行两个整数 n,m。

第二行 n 个整数表示 a_i。

后面 m 行每行为 1\ l\ r\ x 或者 2\ l\ r，分别表示修改和询问。

输出

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

样例

输入

5 5
1 2 3 4 5
2 1 5
1 2 3 4
2 1 5
2 3 3
2 2 4

输出

5
3
1
1

输入

4 5
1 1 4 5
1 3 4 5
2 3 4
1 1 3 4
2 1 4
2 2 2

输出

1
2
1

提示

对于 100\% 的数据，1\leq n , m \leq 10^5，1\leq a_i\leq 10^9。

子任务编号n\leqm\leq特殊性质分值
\text{Subtask 1}50005000无10
\text{Subtask 2}10^510^5无 1 操作15
\text{Subtask 3}5\times 10^45\times 10^41 操作中 l=r15
\text{Subtask 4}10^510^51 操作中 l=r20
\text{Subtask 5}10^510^5无40
时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题