Description
给出一个序列 (a_i),维护两个操作:
1.单点修改
2.查询 ([l,r]) 内每一个元素的在 ([l,r]) 最晚出现位置-最早出现位置 之和
题面
Solution
维护对于每一个 (sum next_{k}-k,next∈[l,r],k∈ [l,r],), 相当于是一个差分的过程
这是一个二维的查询,用树状数组套线段树可以搞定,第一维为 (next), 第二维是 (k)
这样因为有 (k<next_k) 的偏序关系,直接做前缀查询就好了
用 (set) 维护每一种权值的出现位置,然后单点修改就在 (set) 里查前驱后继然后在线段树中减去贡献就好了
懒的写.cpp