遅延セグメント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)$ で処理することができます。

実装例