4091 沙奈朵

题面

内容

沙奈朵给定一个长为 $n$ 的序列 $a$，每个位置是一个 $[1,n]$ 内的整数。

定义 $f(i,j)$ 表示有多少 $x$ 满足 $i\le x<j$ 且 $a_x\neq a_{x+1}$。

有 $m$ 次操作：

1 l r x：表示将 $l$ 位置的元素修改为 $x$。

2 l r x：表示查询区间 $[l,r]$ 中，对任意 $l\le i<j\le r$，且 $a_i=a_j=x$，$f(i,j)$ 的和。

注意，为了让两种操作读入格式一致，$1$ 操作中的 $r$ 变量没有作用。

输入

第一行两个数 $n,m$。

第二行 $n$ 个用空格隔开的数表示序列 $a$。

之后 $m$ 行，每行四个用空格隔开的数 $opt,l,r,x$ 表示一次操作。

输出

对每个 $2$ 操作，输出一行一个数表示答案。

样例1

输入

10 10
2 1 2 1 8 3 2 1 2 2
2 6 9 2
2 3 10 2
2 2 10 2
2 1 3 2
2 4 10 1
1 2 4 2
2 3 10 2
2 2 7 1
2 2 7 2
2 3 6 2

输出

2
20
20
2
4
20
0
8
0

提示

对于 $20\%$ 的数据，满足 $1\le n,m\le 1000$。

对于另外 $20\%$ 的数据，没有 $1$ 操作。

对于另外 $30\%$ 的数据，满足 $1\le n,m\le 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m \le 5\times10^5$，$1\le l\le r\le n$，$1\le a_i,x\le n$，所有输入均为整数。

思路

首先题意是要找一定范围内的每一个小区间，每个小区间的答案是这段区间内不同的值的个数（色块数，同一个数为一个色块，色块数的前缀和需要预处理方便区间查询），然后求这些区间答案的和。

采用分块的思想

把序列分成根号个块，每个块长度大概为$\sqrt(n)$

维护一个$a$代表$i$之前的每个$1$到$i$这个位置的染色段数

用A[x]代表当前位置向左所有答案累积和（类似于前缀和一样的东西）。

用B[x]代表当前位置向右产生所有答案的累计和

用C[x]代表当前块的x的个数

用D[x]代表当前块的答案

当前位置向左累计产生的答案为红色段加和。

每遇到一个$x$就需要将其A累加到当前块的总答案中，

每个颜色其实就是$a$的一种状态，

那么怎么转移呢？

正着把这个区间枚举一遍得到A的值和当前块总共的答案，

合并块的时候，左边的块对于右边会产生答案，右边的块对于左边会产生答案，

查询的时候（临时变量ans）：

ans+=l.A[x]*r.C[x]+r.B[x]*l.C[x]+l.C[x]*r.C[x]*(!l.r==r.l)

如果遇到单点修改，那么就重置一下当前块，复杂度为sqrt(n)，

一开始需要把每个块扫一遍，把每个A,B,C,D都预处理一遍，还要预处理一个区间不同色块数的前缀和，因为从这个点到上一个点产生的答案即为这段区间内色块数，$O(1)$查询。

代码

待补。