YZOJ P3942 gss2加强版

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)\) 。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注