没有传送门。
非常有意思的一道题，都是独立想出来的。
题意
维护一个序列，支持单点修改，查询全局所有长度为 \(k\) 的区间，区间中不同数字个数的和。
序列长度 \(n\)，操作次数 \(m\)，满足 \(n, k, m \leq 3 \times 10 ^ 5\)，序列值域是 \([1,n]\)
思路
只要求求解一个和，很明显要拆贡献。
一个方向是去按照下标拆贡献，看每个位置的值被加入到区间中和被删除时对答案产生的影响，但贡献总是跟 \(k\) 有关，这不利于查询。
换一种思路，按照值域拆贡献，考虑每一个值会对答案产生多少贡献，这样就很好地将不同的值独立开来，解决不同数字的问题。
于是最后的答案就是对于一个值 \(i\) 所有长度为 \(k\) 且包含值 \(i\) 的区间的个数的和。
但是固定一个值，求包含它的区间数量也不好求，可以考虑正难则反，去计算有多少区间是不包含 \(i\) 的，最后用总共的区间个数 \(n - k + 1\) 减一下。
我们发现，一个区间不包含 \(i\) 必定是在 \(i\) 的两个出现位置之间，形式化地，是当前区间 \([l,r]\) 满足：
其中 \(pos\) 是 \(i\) 出现位置的有序序列。
那么对于相邻的两个 \(pos\)，其中包含的区间有 \(\max \left( 0, pos_{j} - pos_{j - 1} - k \right)\) 个。
先考虑不带修改的部分分：
我们将式子转变为 \(\max \left( k, pos_j - pos_{j - 1} \right) - k\)。
就拆成了查询 \(\le k\) 的 \(pos_j - pos_{j - 1}\) 的和以及个数。
不带修的情况只需要把所有的 \(pos_j - pos_{j - 1}\) 排序做后缀和，每次查询二分即可。
加上修改之后，就不能完成排序、后缀和的事情了。
先解决如何查询 \(\le k\) 的 \(pos_j - pos_{j - 1}\) 的和以及个数，同时要支持加入与删除：
平衡树是可以做到的，但是太麻烦，可以用树状数组维护一个序列，下标为 \(i\) 表示 \(pos_j - pos_{j - 1} = i\) 的 \(pos_j - pos_{j - 1}\) 之和。
每次修改就形如 \(add(i,i)\)。
记录这个的个数也类似，只需要把定义改成个数，每次修改形如 \(add(i,1)\) 即可。
那么考虑每一次单点修改 \(a_i \rightarrow v\) 造成的影响，分原来的值（\(pre\_v\)）和新的值（\(cur\_v\)）考虑：
-
\(pre\_v\) 中，\(i\) 与其前驱，\(i\) 与其后驱的差应当删除，而其前驱和其后驱的差应当被加入。
-
\(cur\_v\) 类似，应当删除加入后 \(i\) 的前驱、后驱之间的差删除，将 \(i\) 与其前驱，与其后驱的差考虑。
时间复杂度是 \(O(m \log n)\)。