展品统计

【题目描述】

展馆里有一排 $n$ 件展品，第 $i$ 件展品的类别为 $a_i$．工作人员会选取一段连续的展品作介绍，这段介绍的丰富度，就是其中出现的不同类别的数量．例如，类别依次为 $2,5,2$ 的一段展品，丰富度为 $2$．

展馆接下来要进行 $q$ 次操作，每次操作为以下两种之一：

• 1 p v：将第 $p$ 件展品替换为类别为 $v$ 的展品．
• 2 x：只考虑前 $x$ 件展品，求其中所有非空连续区间的丰富度之和．

具体地，设 $f(l,r)$ 为当前 $a_l,a_{l+1},\ldots,a_r$ 中不同类别的数量，一次 2 x 操作需要求出

操作按输入顺序执行．即使两段区间包含的类别序列相同，只要端点不同，也要分别计入答案．

【输入描述】

第一行包含两个整数 $n,q$，分别表示展品数量和操作次数．

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始的展品类别．

接下来 $q$ 行，每行以一个整数 $op$ 开头：

• 若 $op=1$，这一行接下来包含两个整数 $p,v$，表示一次替换操作．
• 若 $op=2$，这一行接下来包含一个整数 $x$，表示一次询问操作．

保证至少有一次询问．替换后的类别可以与替换前相同．

【输出描述】

对每次询问，按顺序输出一行一个整数，表示丰富度之和．答案不取模．

【样例 1】

【样例 1 输入】

4 6
1 2 1 3
2 3
1 2 1
2 3
2 4
1 4 1
2 4

【样例 1 输出】

9
6
13
10

【样例 1 解释】

第一次询问只考虑 $1,2,1$．长度为 $1$ 的三个区间丰富度均为 $1$，长度为 $2$ 的两个区间丰富度均为 $2$，长度为 $3$ 的区间丰富度为 $2$，总和为 $3+4+2=9$．

第一次替换后，前三件展品的类别均为 $1$，六个非空区间的丰富度均为 $1$，因此第二次询问的答案为 $6$．此时整个序列为 $1,1,1,3$，十个非空区间中有三个同时含有类别 $1$ 和 $3$，因此第三次询问的答案为 $10+3=13$．

最后四件展品的类别全部相同，答案为区间数量 $10$．

【样例 2】

【样例 2 输入】

3 5
8 8 8
2 1
1 2 9
2 3
1 2 9
2 2

【样例 2 输出】

1
9
4

【样例 2 解释】

第一次替换后，序列变为 $8,9,8$，第二次询问的答案为 $3+4+2=9$．第二次替换没有改变序列．最后一次询问只考虑 $8,9$，三个区间的丰富度分别为 $1,1,2$，答案为 $4$．

【下发样例】

见选手目录下的 Data/sample3.in 与 Data/sample3.ans，以及其他同名输入、答案文件．

【数据规模与约定】

对于所有测试数据，保证 $1\le n,q\le 2\times10^5$，$1\le a_i,v\le 2\times10^5$，$1\le p,x\le n$，$op\in\{1,2\}$．

本题采用子任务评测；只有通过一个子任务中的全部测试数据，才能获得该子任务的分数．各子任务独立计分．

特殊性质 A：初始时以及每次替换操作后，对于每一种在序列中出现的类别，它的所有出现位置恰好构成一个连续区间．例如，$1,1,3,3,2$ 满足该性质，而 $1,3,1$ 不满足．

【大样例下载链接】

点击下载本题选手目录