CF1423G Growing flowers

Sarah 一直热爱大自然。几年前，她攒够了钱，环游世界，探索大自然在地球上创造的一切。在这段时间里，她参观了一些数百年来未被触及的特殊地方，从在严寒中观赏冰山，到在海洋中潜水欣赏那些未被发现的海洋生物。这些经历因山脉经年累月形成的壮丽景色而更加令人惊叹，吸引着游客们年复一年地前来观赏。随着时间推移，这些探险让 Sarah 感到疲惫，最终她决定在郊区安定下来，过上平静的生活。 然而，Sarah 对大自然的热爱从未消退。她开始在自家花园里种花，以此与自然保持联系。起初她只种植蓝色兰花，但随着时间推移，她开始种植不同种类的花卉，为花园增添多样性。这些花可以用一个长度为 $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$ 朵花的“美丽度”定义为该段中不同花的种类数。整个花园的美丽度为所有连续 $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$，表示 Sarah 将第 $L$ 到第 $R$ 朵花全部更换为类型 $X$。即对于所有 $i$ 满足 $L \leq i \leq R$，有 $A[i] = X$。 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$），表示每朵花的类型。 接下来的 $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, 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]$，同样有三种不同的花，$B_2 = 3$。所以总美丽度 $B = B_1 + B_2 = 3 + 3 = 6$。 第四次操作后，花园变为 $[5, 5, 5, 5, 5]$。 第五次查询 $K = 2$，此时所有四段都是 $[5, 5]$，每段只有一种花，美丽度为 $1$，总美丽度 $B = B_1 + B_2 + B_3 + B_4 = 1 + 1 + 1 + 1 = 4$。 由 ChatGPT 4.1 翻译