题解 CF1679B【Stone Age Problem】

## 题意 给你一个长度为 $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` 的写法简洁不少。 [珂朵莉树做法代码](https://www.luogu.com.cn/paste/tf180kku) ## 更优的做法 虽然珂朵莉树的做法可以过，但有点碰运气的成分。其实此题还有无需数据结构的做法。 只需记录每个位置上次修改的时间戳（`lastSingle[i]`）、以及上一次全局修改是什么时候、修改成了什么即可（`lastAll`，`lastAllVal`）。 同时维护整个数列的和：若是全局修改，新的数列和是 $n\times x$；如果是单点修改，判断修改的位置之前是什么（利用时间戳），然后加加减减即可。 时间复杂度 $O(n+q)$，额外空间复杂度 $O(n)$。 ```cpp 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); } } ```