← 返回题目列表

Codeforces · 1423/G

G. 种花

中文机器翻译题面 查看原题

莎拉一直是大自然的爱好者,几年前,她攒了足够的钱环游世界,探索大自然在地球上一生所建造的所有事物。在此期间,她参观了一些真正特殊的地方,这些地方几个世纪以来都没有被触及,从在寒冷的天气中观看冰山到在海洋中水肺潜水以及欣赏看不见的海洋生物。随着时间的推移,山脉所形成的令人惊叹的景色增强了这些体验,并让游客可以连续多年观看。随着时间的推移,所有这些探险都对莎拉造成了影响,最终她决定在郊区定居并过上平静的生活。

然而,由于莎拉对自然的热爱从未消退,她开始在花园里种植花卉,试图与自然保持联系。一开始,她只种植蓝色兰花,但随着时间的推移,她开始使用不同的花卉类型,为她的花卉收藏增添多样性。这个花的集合可以表示为 $$$N$$$ 花的数组,其中第 $$$i$$$ 有一个与之关联的类型,表示为 $$$A_i$$$。每个居民在路过她的收藏品时,由于视野的宽度有限,在每个时刻只能看到 $$$K$$$ 连续的花朵。要查看整个集合,居民将查看前 $$$K$$$ 连续花朵 $$$A_1, A_2, ..., A_K$$$,然后将其视图移动一朵花并查看 K 连续花朵的下一部分 $$$A_2, A_3, ..., A_{K+1}$$$ 等等,直到扫描整个集合,以部分 $$$A_{N-K+1}, ..., A_{N-1},A_N$$$。

每个居民将 $$$K$$$ 花朵区域的美丽程度确定为该区域中不同花朵类型的数量。此外,整个集合的美丽度是通过将每个连续部分的美丽度值相加来计算的。形式上,从第 $$$i$$$ 位置开始的部分的美丽度 $$$B_i$$$ 计算为 $$$B_i =distinct(A_i, A_{i+1}, ..., A_{i+K-1})$$$,并且集合 $$$B$$$ 的美丽度计算为 $$$B=B_1 + B_2 + ... + B_{N-K+1}$$$。

另外,由于Sarah想让她收集的鲜花保持新鲜感,她还可以挑选两个点$$$L$$$和$$$R$$$,将鲜花放置在这两个点之间并种植新花,所有花都是同一类型。

您将收到 $$$Q$$$ 查询,每个查询都属于以下两种类型:

1. 您将获得三个整数 $$$L、R、X$$$,描述莎拉在位置 $$$L$$$ 和 $$$R$$$(含)之间种植了 $$$X$$$ 类型的花。正式的集合被更改为 $$$A[i]=X$$$ 对于 $$$[L.. R]$$$ 范围内的所有 $$$i$$$。
2. 您将获得整数 $$$K$$$,即居民视野的宽度,您必须确定居民与该集合关联的美丽值 $$$B$$$

对于第二类型的每个查询,打印结果 – 集合的美丽$$$B$$$。

输入

第一行包含两个整数 $$$N$$$ 和 $$$Q \;(1 \leq N, Q \leq 10^5)\,$$$ — 分别是花的数量和查询的数量。

第二行包含 $$$N$$$ 整数 $$$A_1, A_2, ..., A_N\;(1 \leq A_i \leq 10^9)\,$$$ — 其中 $$$A_i$$$ 表示第 $$$i$$$ 朵花的类型。

接下来的 $$$Q$$$ 行描述查询并以整数 $$$T\in\{1, 2\}$$$ 开头。

- 如果 $$$T = 1$$$,$$$L, R, X\;(1 \leq L, R \leq N;\; 1 \leq X \leq 10^9)\,$$$ — $$$L$$$ 和 $$$R$$$ 描述边界,$$$X$$$ 描述花类型,行中还会有三个整数
- 如果 $$$T = 2$$$,则 $$$K\;(1 \leq K \leq N)\,$$$ — 居民视野宽度会多一个整数

输出

对于第二类型的每个查询,打印集合的美丽$$$B$$$。

示例

输入 #1

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

输出 #1

9
6
4

注意

让我们看一下这个例子。

最初集合为 $$$[1, 2, 3, 4, 5]$$$。在第一个查询 $$$K = 3$$$ 中,我们考虑三朵花的部分,第一朵花是 $$$[1, 2, 3]$$$。由于该部分的美丽程度是该部分中不同花卉类型的数量,因此 $$$B_1 = 3$$$。第二部分是 $$$[2, 3, 4]$$$ 和 $$$B_2 = 3$$$。第三部分是 $$$[3, 4, 5]$$$ 和 $$$B_3 = 3$$$,因为花的类型都是不同的。居民与该收藏相关的美丽值是$$$B = B_1 + B_2 + B_3 = 3 + 3 + 3 = 9$$$。

第二次查询后,集合变为$$$[5, 5, 3, 4, 5]$$$。

对于第三个查询 $$$K = 4$$$,因此我们考虑四朵花的部分,第一朵花是 $$$[5, 5, 3, 4]$$$。本节中有三种不同的花类型 $$$[5, 3, 4]$$$,因此 $$$B_1 = 3$$$。第二部分 $$$[5, 3, 4, 5]$$$ 也有 $$$3$$$ 不同的花类型,因此 $$$B_2 = 3$$$。居民与该收藏相关的美丽值是$$$B = B_1 + B_2 = 3 + 3 = 6$$$

第四次查询后,集合变为$$$[5, 5, 5, 5, 5]$$$。

对于第五个查询 $$$K = 2$$$,在这种情况下,所有四个部分都相同,每个部分都是 $$$[5, 5]$$$。 $$$[5, 5]$$$ 的美妙之处在于 $$$1$$$,因为此部分 $$$[5]$$$ 中只有一个不同的元素。整个集合的美丽是$$$B = B_1 + B_2 + B_3 + B_4 = 1 + 1 + 1 + 1 = 4$$$