1 条题解
信息
- ID
- 80
- 时间
- 1000~7500ms
- 内存
- 64~70MiB
- 难度
- 6
- 标签
- 递交数
- 7
- 已通过
- 1
- 上传者
给自己的题来一篇题解吧还是,反正是模板。
推一下柿子:a×b,当 a←a+k,b←b+w时,显然有 (a+k)×(b+w)=a×b+a×w+k×b+k×w,作差得增量为 a×w+k×b+k×w。 推广到区间和,设区间长度也就是区间内元素个数为 len,∑a×b 的增量显然为 (∑a)×w+k×(∑b)+k×w×len,别忘了更新 ∑a 和 ∑b,以及更新的顺序。
推出来柿子之后是好维护的,线段树或者分块都可以,要注意本题卡了空间,请手动给线段树分配儿子指针以做到严格的 2n 空间复杂度,真不想这么干的话写分块也可以,手动调调块长吊锤线段树。
注册一个 PYYG 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。