题解 CF1679B【Stone Age Problem】

2022-05-15 21:08:41


题意

给你一个长度为 $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])、以及上一次全局修改是什么时候、修改成了什么即可(lastAlllastAllVal)。

同时维护整个数列的和:若是全局修改,新的数列和是 $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);
  }
}