Description:


墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?

Input:


第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。

Output:


对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input:


Sample Output:


题解:


貌似这是一道带修改莫队的题目,然而我是用分块做的~

对于第一种操作,还是很好做的,对于每一个位置i记录pre[i]表示c[i]上一次出现的位置,那么所有[L, R]中 \(pre[i]\lt L\) 的个数就是不同的颜色数,对于同一个块中的直接暴力,每一个块维护另外一个s数组,为把pre[i]排序后的结果,那么对于整块的操作可以直接在s中二分查找L。

对于第二种操作,由于操作数比较少,我们可以直接暴力重构数组~

貌似比较简单~