CF848C Goodbye Souvenir

发表于 更新于 分类于 ， ， 阅读次数：

题意：对于序列 ，记 为 去重后的集合， 为 在 中的第一次出现位置， 为最后一次出现位置。定义 的权值为 给出序列 ，支持：

  • 单点修改
  • 求

允许离线，，时限 。

设 为上一个与 相等的位置。

将 的权值设为 ，把区间内的权值求和，就能得到：最后一次出现的位置 第一次出现的前继。

然后，我们要减去多余的 “第一次出现的位置它的前继”。

这也好办，计算 即可。这是个二维数点。

带修改的话，拿 std::set 维护 ，离线成三维偏序，然后写个 CDQ 就做完了。