mengbierr

一个蒟蒻的博客

5月22

51nod 1712 区间求和

分开考虑每个数被加和减了多少次。
考虑加,统计当前答案,从后往前,每次指针移动一位,答案减少所在区间个数,增加距离所有新增加的区间的左端点距离和个,增加的值用前缀和简单维护即可,减少的值计算一下后一位区间个数-与前面当前值相同的数的个数+后面与当前值相同的数的个数。
减的次数相反,不多说了…

发表评论

电子邮件地址不会被公开。 必填项已用*标注