题意

给你一个长度为 $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);
  }
}