CF1423G.Growing flowers

Sarah has always been a lover of nature, and a couple of years ago she saved up enough money to travel the world and explore all the things built by nature over its lifetime on earth. During this time she visited some truly special places which were left untouched for centuries, from watching icebergs in freezing weather to scuba-diving in oceans and admiring the sea life, residing unseen. These experiences were enhanced with breathtaking views built by mountains over time and left there for visitors to see for years on end. Over time, all these expeditions took a toll on Sarah and culminated in her decision to settle down in the suburbs and live a quiet life.

However, as Sarah's love for nature never faded, she started growing flowers in her garden in an attempt to stay connected with nature. At the beginning she planted only blue orchids, but over time she started using different flower types to add variety to her collection of flowers. This collection of flowers can be represented as an array of $N$ flowers and the $i$-th of them has a type associated with it, denoted as $A_i$. Each resident, passing by her collection and limited by the width of his view, can only see $K$ contiguous flowers at each moment in time. To see the whole collection, the resident will look at the first $K$ contiguous flowers $A_1, A_2, ..., A_K$, then shift his view by one flower and look at the next section of K contiguous flowers $A_2, A_3, ..., A_{K+1}$ and so on until they scan the whole collection, ending with section $A_{N-K+1}, ..., A_{N-1}, A_N$.

Each resident determines the beautiness of a section of $K$ flowers as the number of distinct flower types in that section. Furthermore, the beautiness of the whole collection is calculated by summing the beautiness values of each contiguous section. Formally, beautiness $B_i$ of a section starting at the $i$-th position is calculated as $B_i = distinct(A_i, A_{i+1}, ..., A_{i+K-1})$, and beautiness of the collection $B$ is calculated as $B=B_1 + B_2 + ... + B_{N-K+1}$.

In addition, as Sarah wants to keep her collection of flowers have a fresh feel, she can also pick two points $L$ and $R$, dispose flowers between those two points and plant new flowers, all of them being the same type.

You will be given $Q$ queries and each of those queries will be of the following two types:

1. You will be given three integers $L, R, X$ describing that Sarah has planted flowers of type $X$ between positions $L$ and $R$ inclusive. Formally collection is changed such that $A[i]=X$ for all $i$ in range $[L.. R]$.
2. You will be given integer $K$, width of the resident's view and you have to determine the beautiness value $B$ resident has associated with the collection

For each query of second type print the result – beautiness $B$ of the collection.

莎拉一直热爱大自然，几年前她积攒了足够的资金环游世界，探索地球上历经漫长岁月由自然之力所创造的一切奇观。在此期间，她游览了一些真正特别的地方——这些地方数百年来都未受人类干扰：从在严寒天气中观赏冰山，到潜入海洋深处欣赏隐匿于水下的海洋生物；还有那些经年累月由山脉塑造而成、壮丽非凡的景观，静待游客世代瞻仰。然而，长年累月的探险之旅终究对莎拉造成了损耗，最终促使她决定定居于市郊，过上宁静的生活。

尽管如此，莎拉对大自然的热爱从未减退。为了继续保持与自然的联结，她开始在自家花园中种植花卉。起初，她只栽种蓝色兰花；但随着时间推移，她逐渐引入多种不同种类的花卉，以丰富自己的花圃。这一花圃可被建模为一个长度为 $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 = \text{distinct}(A_i, A_{i+1}, ..., A_{i+K-1}),$$

而整片花圃的美丽值 $B$ 则计算为

$$B = B_1 + B_2 + \cdots + B_{N-K+1}.$$

此外，为了让花圃始终保持清新感，莎拉还可以选定两个位置 $L$ 和 $R$，清除其间（含端点）的所有花卉，并重新栽种同一种类的新花。

你将收到 $Q$ 个查询，每个查询属于以下两种类型之一：

1. 给定三个整数 $L, R, X$，表示莎拉已在位置 $L$ 至 $R$（含端点）之间栽种了种类为 $X$ 的花卉。形式化地，数组更新为对所有 $i \in [L..R]$，令 $A[i] = X$。
2. 给定整数 $K$（即居民的视野宽度），你需要计算当前花圃的美丽值 $B$。

对于每个第二类查询，请输出结果——即花圃的美丽值 $B$。

First line contains two integers $N$ and $Q \;(1 \leq N, Q \leq 10^5)\,$ — number of flowers and the number of queries, respectively.

The second line contains $N$ integers $A_1, A_2, ..., A_N\;(1 \leq A_i \leq 10^9)\,$ — where $A_i$ represents type of the $i$-th flower.

Each of the next $Q$ lines describe queries and start with integer $T\in{1, 2}$.

• If $T = 1$, there will be three more integers in the line $L, R, X\;(1 \leq L, R \leq N;\; 1 \leq X \leq 10^9)\,$ — $L$ and $R$ describing boundaries and $X$ describing the flower type
• If $T = 2$, there will be one more integer in the line $K\;(1 \leq K \leq N)\,$ — resident's width of view

第一行包含两个整数 $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)$ —— 表示居民的视野宽度。

For each query of the second type print the beautiness $B$ of the collection.

对于每个第二类查询，输出该集合的美观度 $B$。

Let's look at the example.

Initially the collection is $[1, 2, 3, 4, 5]$. In the first query $K = 3$, we consider sections of three flowers with the first being $[1, 2, 3]$. Since beautiness of the section is the number of distinct flower types in that section, $B_1 = 3$. Second section is $[2, 3, 4]$ and $B_2 = 3$. Third section is $[3, 4, 5]$ and $B_3 = 3$, since the flower types are all distinct. The beautiness value resident has associated with the collection is $B = B_1 + B_2 + B_3 = 3 + 3 + 3 = 9$.

After the second query, the collection becomes $[5, 5, 3, 4, 5]$.

For the third query $K = 4$, so we consider sections of four flowers with the first being $[5, 5, 3, 4]$. There are three distinct flower types $[5, 3, 4]$ in this section, so $B_1 = 3$. Second section $[5, 3, 4, 5]$ also has $3$ distinct flower types, so $B_2 = 3$. The beautiness value resident has associated with the collection is $B = B_1 + B_2 = 3 + 3 = 6$

After the fourth query, the collection becomes $[5, 5, 5, 5, 5]$.

For the fifth query $K = 2$ and in this case all the four sections are same with each of them being $[5, 5]$. Beautiness of $[5, 5]$ is $1$ since there is only one distinct element in this section $[5]$. Beautiness of the whole collection is $B = B_1 + B_2 + B_3 + B_4 = 1 + 1 + 1 + 1 = 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]$ 同样包含三种不同的花种类，因此 $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$。