seuOJ565 - 猫娘的咒语

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：256 MiB
• 题目标签：

题目描述

众所周知，Lambda是一名可爱的猫娘魔法少女，她会很多很多的法术。

Lambda生成了一个长度为 $n$ 的序列。

因为只有一个序列不够她练习，所以在接下来的 $m$ 秒里，她要么会思考一个问题，要么会再念出一段咒语。

询问有一种：

• 询问区间 $[l,r]$ 中等于 $x$ 的数有多少个。

咒语有两种：

• 第一种咒语：将区间 $[l,r]$ 中所有的 $x$ 更改为 $y$。

• 第二种咒语：将区间 $[l,r]$ 上所有的数加上 $x$。

虽然Lambda擅长魔法，但她并不擅长计算，于是就只好向你请教询问，你需要回答Lambda的每一个询问，否则魔法少女生气的后果是很严重的。

输入格式

第一行两个数 $n,m$，表示序列长度和时间。

第二行 $n$ 个数，给出Lambda生成的序列 $a$。

接下来 $m$ 行，每行的第一个数 $op$ 表示类型：

• 若 $op=0$，那么接下来输入 $l,r,x$ ，表示询问的参数。
• 若 $op=1$ 接下来输入 $l,r,x,y$ 表示第一种咒语的参数。
• 若$op=2$ 接下来输入 $l,r,x$，表示第二种咒语的参数。

输出格式

对于每个询问，你需要在单独的一行输出这个询问的答案。

样例

输入 #1

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

输出 #1

1
2
2

解释 #1

• 第一秒，询问 $[1, 2]$ 中 $1$ 的数量，序列为 $1, 4, 5$，询问区间为 $1,4$，答案为 $1$。
• 第二秒，把 $[2,3]$ 中所有 $4$ 改为 $1$，序列变为 $1,1,5$。
• 第三秒，询问 $[1, 2]$ 中 $1$ 的数量，序列为 $1, 1, 5$，询问区间为 $1,1$， 答案为 $2$。
• 第四秒，把 $[1,3]$ 中所有数加上 $4$，序列变为 $5,5,9$。
• 第五秒，询问 $[1, 3]$ 中 $5$ 的数量，序列为 $5, 5, 9$，询问区间为 $5,5,9$，答案为 $2$。

数据范围与提示

对于所有数据 $1\le n,m,a_i,y\leq10^5,1\leq l\leq r\leq n, 0\le|x|\le10^5$。并且保证任何时候 $1\leq a_i\leq 10^5$。