遅延セグメントtreeを使って解きます。

まず、 \(D_{x}=\sum_{i=1}^{x}C_{x}=\sum_{i=1}^{x}(x+1-i)B_{x}\) です。

ここで、 \(E_{l,r}=\sum_{i=l}^{r-1}(r-i)B_{i}\) さらに、\(F_{l,r}=\sum_{i=l}^{r-1}B_{i}\) と定義します。

\(D_{x}=E_{1,(x+1)}\) となるため、この \(E_{l,r}\) を求めることができれば良いです。

ここで、 \(E_{l,k},E_{k,r},F_{l,k},F_{k,r} (l\leq k\leq r)\) がわかっているとき、以下が成り立ちます。

• \(E_{l,r}=E_{l,k}+E_{k,r}+(r-k)F_{l,k}\)

• \(F_{l,r}=F_{l,k}+F_{k,r} \)

また、\(i=l,l+1,...r-2,r-1\) に対して \(B_{i}+=dif\) をすると、\(E_{l,r}, F_{l,r}\) は以下のように変化します。

• \(E_{l,r}+=dif\frac{(r-l)(r-l+1)}{2}\)

• \(F_{l,r}+=(r-l)dif\)

\(A_{x}\leftarrow v\) というクエリは、\(dif=v-A_{x}\) とおくことで、 \(i=x,x+1,...N\) に対して \(B_{i}+=dif\) とするクエリと置き換えることができるので、\((E_{l,r},F_{l,r},r-l)\) をノードにもつ遅延セグメントtreeを使用することで、二つのクエリを一つ当たり \(O(\log N)\) で処理することができます。

実装例