YZOJ P3942 gss2加强版

时间限制：2000MS      内存限制：524288KB

难度：$7.0$

• 题目描述

给你 $n$ 个数，你需要支持一下两种操作。

U x y：将第 $x$ 个数修改成 $y$ ；

Q x y：计算从第 $x$ 个数至第 $y$ 个数中不同数的和并输出。如对于一段数 $1,2,3,2,7$，它的值是 $13=1+2+3+7$ 。

• 输入格式

第一行 $n$ 表示数的个数；

第二行包含这 $n$ 个数；

第三行 $m$ 表示操作次数；

接下来 $m$ 行每行三个数表示题目描述的操作。

• 输出格式

对于每个 Q 操作返回一个值。

• 样例输入

• 样例输出

• 数据规模与约定

所有的输入均在 int  以内。

$n \leq 100000 , m \leq 100000$

 

 

Source： BZOJ 2883

---

 

 

 

思想类似于 P3706 ，求区间内不同数的和 等价于 区间内第一次出现的数的和。

所以可以维护每个位置上 上一个与它数值相同的位置 $pre$，对于区间 $[l, r]$ ，若有 $pre < l$ 则可以加入答案。

显然修改时会影响到其它位置的前驱，所以对于每种数用 std::set  维护相同数的位置。

询问相当于把每个位置看成二维坐标系中的一个点 $\left(pre,i\right)$ ，并求 $x \in [0, l-1], y \in [l, r]$ 的所有点的 $a_i$ 之和。

显然可以用二维线段树维护。

还有一种线段树套平衡树的做法，空间复杂度会比较小。

时间复杂度都为 $O(n \log^2 n)$ 。