我永远喜欢数据结构。
给出长度为 \(n\) 的序列 \(a_1\sim a_n\)，有 \(q\) 次操作：
\(1\texttt{ }l\texttt{ }r\texttt{ }c\)，对于 \(i\in [l,r]\)，执行 \(a_i\leftarrow c\)。
\(2\texttt{ }x\)，查询所有长度为 \(x\) 的子区间中数的种数和。即：
\[\sum\limits_{i=1}^{n-x+1}\sum_{j\in V} [\exists \,k\in [i,i+x-1],a_k=j] \]其中 \(V\) 为值域。
\(n,q\le 10^5\)，\(|V|\le 10^9\)。
\(4.00\,\text{s}\,/\,250.00\,\text{MB}\)。
下文称数为颜色。
tags：
-
\(\text{data structures}\)
-
\(\color{maroon}*3500\)
3k5 纯 DS 太酸爽了。
来一篇没那么感性的题解。
一句话题解：正难则反，考虑贡献。说了和说了一样。
先离散化，考虑改写一下式子：
\[\begin{aligned}\sum\limits_{i=1}^{n-x+1}\sum_{j\in V} [\exists \,k\in [i,i+x-1],a_k=j]&= \sum\limits_{j\in V} \sum\limits_{i=1}^{n-x+1}[\exists \,k\in [i,i+x-1],a_k=j]\\&= \sum\limits_{j\in V} \left(n-x+1-\sum\limits_{i=1}^{n-x+1}[\nexists \,k\in [i,i+x-1],a_k=j]\right)\\&= |V|\cdot (n-x+1)-\sum\limits_{j\in V} \sum\limits_{i=1}^{n-x+1}[\nexists \,k\in [i,i+x-1],a_k=j]\end{aligned} \]维护一个数组 \(b_x\) 表示 \(\sum\limits_{j\in V}\sum\limits_{i=1}^{n-x+1}[\nexists \,k\in [i,i+x-1],a_k=j]\)，则答案为 \(|V|\cdot (n-x+1)-b_x\)。
考虑 \(b_x\) 的含义是什么，就是对于每种颜色，求出原数组中有多少个长度为 \(x\) 的子区间不包含它，然后将这些个数加起来。
我们再考虑对于当前序列构造一个 \(|V|\times n\) 的带权网格 \(A\)。其中：
\[A_{i,j}=\begin{cases}1,a_j=i\\0,\text{otherwise}\end{cases} \]那么 \(b_x\) 就等于这个网格中横向的、长度为 \(\boldsymbol{x}\) 的全 \(\boldsymbol 0\) 连续段个数（下文简称为空连续段）。因为艾弗森括号内的式子等价于网格中这个连续段的值全部为 \(0\)。
注意到当网格是由当前序列构造而成时，\(b_x\) 才有如上含义。但是对于任意一个网格，不管它是否由当前序列构造而成，⌈长度为 \(x\) 的空连续段个数⌋ 这个量都是有意义的。因此再引入一个数组 \(d_x\) 表示当前网格中长度为 \(\boldsymbol x\) 的空连续段个数。
看到 \(1\) 操作是区间推平的形式，考虑使用珂朵莉树维护。我们发现区间推平相当于对于 \(c\) 颜色删去了一些空连续段，又对于区间内的其它颜色加入了一些空连续段。
此处 ⌈删去一个空连续段⌋ 的定义是将该段内的所有 \(0\) 变成 \(1\)。
我们只需要维护每次增 / 删空连续段后的 \(A\) 网格 / \(d\) 数组，就可以得到增 / 删完这么多次，即推平后的序列对应的 \(A\) 网格 / \(d\) 数组。此时 \(d\) 数组和 \(b\) 数组相同，就可以拿它去计算答案了。
而且初始序列对应的 \(A\) 网格 / \(d\) 数组也可以通过 ⌈一个初始全 \(1\) 的网格，先把每一行全部变成 \(0\)，再对于 \(i\in [1,n]\)，执行 \(A_{a_i,i}\leftarrow 1\)⌋ 这样的方式构造出来。
考虑一次增 / 删操作对于 \(d\) 数组而言到底是怎样变化。
-
设增加一个长度为 \(L\) 的空连续段，则对于 \(x>l\)，\(d_x\) 无变化。对于 \(x\in[1,l]\)，\(d_x\) 增加了 \(L-x+1\)。因为多出了这么多可供选择的左端点。
-
设删除一个长度为 \(L\) 的空连续段，则对于 \(x>l\)，\(d_x\) 无变化。对于 \(x\in[1,l]\)，\(d_x\) 减少了 \(L-x+1\)。因为少了这么多可供选择的左端点。
我们发现对于 \(d\) 数组的修改是一个 ⌈区间加等差数列⌋ 的形式。因此实际上要支持的操作是 ⌈区间加等差数列⌋ 和 ⌈单点查询⌋。考虑维护 \(d\) 数组的差分数组，即可转变成区间加定值和区间求和。线段树维护即可。
考虑一次推平操作具体是怎样增 / 删空连续段。首先考虑非空连续段怎么变。
-
对于 \(c\) 颜色，先将其在 \([l,r]\) 内的非空连续段删去，再增加一个 \([l,r]\) 的非空连续段。
-
对于其它颜色，将其再 \([l,r]\) 内的非空连续段删去。
考虑这样引起了怎样的空连续段的变化。
-
对于某种颜色删去一个非空连续段 \([l,r]\) 时，考虑找到它的非空连续段前驱 \([l_1,r_1]\) 和后继 \([l_2,r_2]\)。那么相当于先删去 \((r_1,l)\) 和 \((r,l_2)\) 两个空连续段，再增加 \((r_1,l_2)\) 这个空连续段。
-
对于某种颜色加入一个非空连续段 \([l,r]\) 时，同样考虑找到它的前驱、后继，那么相当于先删去 \((r_1,l_2)\) 这个空连续段，再加入 \((r_1,l)\) 和 \((r,l_2)\) 这两个空连续段。
因为要支持找前驱、后继，考虑对每种颜色（即网格的每一行）开一个 set 按顺序存储非空连续段。
这样我们就知道如何维护区间推平后的 \(A\) 网格以及 \(d\) 数组的。
查询平凡，对于差分数组单点查询即可。然后带入式子得到答案。
时间复杂度可以这么分析：
-
初始有 \(\mathcal{O}(n)\) 个连续段，每次操作加入 \(\mathcal{O}(1)\) 个连续段，一共有 \(\mathcal{O}(n+m)\) 个连续段。
-
一个连续段只有在插入 / 删除时才会进行操作，共 \(\mathcal{O}(1)\) 次。一次操作有 \(\mathcal{O}(1)\) 次
set上二分以及线段树区间修改，时间复杂度为 \(\mathcal{O}(\log n)\)。 -
所以修改操作的时间复杂度为 \(\mathcal{O}((n+m)\log n)\)，查询操作的时间复杂度为 \(\mathcal{O}(m\log n)\)，因此总时间复杂度为 \(\mathcal{O}((n+m)\log n)\)，常数巨大。
可能是我#define int long long的原因。
空间复杂度显然为 \(\mathcal{O}(n+m)\)。至此问题得到解决。
提交记录（\(\color{limegreen} \bf Accepted\)，\(\boldsymbol{2.23 \,\text{s}\,/\, 32.94\,\text{MB}}\)，含代码）
标签：limits,sum,网格,CF1423G,连续,数组,Growing,mathcal,flowers From： https://www.cnblogs.com/MnZnOIerLzy/p/17861475.html