1 条题解

  • 0
    @ 2023-9-28 18:53:32

    给自己的题来一篇题解吧还是,反正是模板。

    推一下柿子:a×ba\times b ,当 aa+k,bb+wa\leftarrow a+k,b\leftarrow b+w时,显然有 (a+k)×(b+w)=a×b+a×w+k×b+k×w(a+k)\times (b+w)=a\times b+a \times w+k \times b+k\times w,作差得增量为 a×w+k×b+k×wa \times w+k \times b+k\times w。 推广到区间和,设区间长度也就是区间内元素个数为 lenlena×b\sum a\times b 的增量显然为 (a)×w+k×(b)+k×w×len(\sum a) \times w+k \times (\sum b)+k\times w\times len,别忘了更新 a\sum ab\sum b,以及更新的顺序。

    推出来柿子之后是好维护的,线段树或者分块都可以,要注意本题卡了空间,请手动给线段树分配儿子指针以做到严格的 2n2n 空间复杂度,真不想这么干的话写分块也可以,手动调调块长吊锤线段树。

    Shiroko&Sensei/【模板】区间点积和

    信息

    ID
    80
    时间
    1000~7500ms
    内存
    64~70MiB
    难度
    6
    标签
    递交数
    7
    已通过
    1
    上传者