牛客练习赛130 C 题解

思路分析

观察一下这个式子，我们发现，遍历 来计算贡献每个 对于答案的贡献是 。每个 对于答案的贡献是 。

原因是，对于每个 我们找到它可能产生贡献的位置都在 之后，所以是一个后缀和。对于 同理。

但是这个题带修改，所以我们采用两个树状数组来维护 与 的前缀和，然后差分区间查询即可。