xmoj-3332

· · 个人记录

首先，意识到前缀和的前缀和的意义

SS_{i}=\sum_{j=1}^{i}\sum_{k=1}^{j}a_{k}

考虑每一个a_{k}对答案的贡献，得

SS_{i}=\sum_{j=1}^{i}(i-j+1)a_{j}

分离正负，提取已知的i

SS_{i}=(i+1)\sum_{j=1}^{i}a_{j}-\sum_{j=1}^{i}ja_{j}

因为点修+区查，所以使用树状数组维护，一个维护a_{j}，另一个维护ja_{j}