题意
给你一个长度为 $n$ 的数列 $a$,进行 $q$ 次操作。操作有三种:
- 把 $a_i$ 赋值为 $x$;
- 把 $a$ 中所有数字赋值为 $x$;
-
查询 $a$ 的所有元素和。
$n, q \leq 2\times 10^5$。
分析
看到第二种操作(区间推平),想到珂朵莉树。
虽然此题数据不保证随机,但是只有单点修改和区间赋值两种修改操作,且所有的查询操作范围都一致,所以还是可以跑过去的。
顺带一提,由于珂朵莉树的每个区间都是相邻的,后一个区间的左端点等于前一个区间的右端点,所以珂朵莉树也可以用 std::map
来实现——
用二元组 $[l, val]$ 表示珂朵莉树的每个区间,使用 std::map<int, int>
存储。key
是区间的左端点,value
是区间的值。这比 set
的写法简洁不少。
更优的做法
虽然珂朵莉树的做法可以过,但有点碰运气的成分。其实此题还有无需数据结构的做法。
只需记录每个位置上次修改的时间戳(lastSingle[i]
)、以及上一次全局修改是什么时候、修改成了什么即可(lastAll
,lastAllVal
)。
同时维护整个数列的和:若是全局修改,新的数列和是 $n\times x$;如果是单点修改,判断修改的位置之前是什么(利用时间戳),然后加加减减即可。
时间复杂度 $O(n+q)$,额外空间复杂度 $O(n)$。
void solution() {
int n, q;
read(n, q);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) read(a[i]);
ll s = std::accumulate(a.begin() + 1, a.end(), 0ll);
int lastAll = -1, lastAllVal = -1;
std::vector<int> lastSingle(n + 1);
for (int _ = 1; _ <= q; ++_) {
int opt;
read(opt);
if (opt == 1) {
int idx, x;
read(idx, x);
s -= lastSingle[idx] < lastAll ? lastAllVal : a[idx];
s += x;
lastSingle[idx] = _;
a[idx] = x;
} else {
int x;
read(x);
lastAll = _;
lastAllVal = x;
s = 1ll * x * n;
}
print(s);
}
}