RT,题面如下:
给定一个长为 n 的序列 a1,⋯,an(初始全为 0),m 次操作,每次给定 l,r,k,对 [l,r] 内的每个 i 都令 ai 加上 (ki−l+k)。最后输出整个序列,对 109+7 取模。
n,m≤5×105,0≤k≤20
容易发现加的这个东西实际上是序列 1,1,1,⋯ 的 k 阶前缀和的前 r−l+1 项,所以考虑建立 1 到 k 阶的差分数组,转换为单点修改。
那么关键在于如何在高阶差分数组中将修改限制在区间内。我手推了一个 k=3 的情况:
0,1,3,6,10,15,0,0,0 (Δ0)
0,1,2,3,4,5,−15,0,0 (Δ1)
0,1,1,1,1,1,−20,15,0 (Δ2)
0,1,0,0,0,0,−21,35,−15(Δ3)
然后把后面的补项列出来:
−Cr−l+kk
−Cr−l+kk−Cr−l+k−1k−1,Cr−l+kk
−Cr−l+kk−Cr−l+k−1k−1−Cr−l+k−2k−2,2Cr−l+kk+Cr−l+k−1k−1,−Cr−l+kk
抽象一下,后续大概是这样:
(−1,−1,−1,−1),(3,2,1),(−3,−1),(1)
(−1,−1,−1,−1,−1),(4,3,2,1),(−6,−3,−1),(4,1),(−1)
(−1,−1,−1,−1,−1,−1),(5,4,3,2,1),(−10,−6,−3,−1),(10,4,1),(−5,−1),(1)
到这里我会 O(nk2) 了,请问大佬怎么砍掉一个 k……