差分更新示例

当 $b_i\geq k$。此时对于前半段的影响不会在 $1$ 的左侧。

• 定义 $l=b_i-k+1$，则 $a_l\gets a_l+1$。

因此需要更新：

• $c_l\gets c_l+1$
• $c_{b_i+1}\gets c_{b_i+1}-2$

当 $b_i<k$。此时对于前半段的影响会在 $a_1$ 的左侧产生。

因此 $a_1\gets a_1+k-(b_i-1)$。例如当 $k=5,b_i=3$ 时，$a_1\gets a_1+5-2=3$。

因此需要更新：

• $c_1\gets c_1+k-(b_i-1)$
• $c_2\gets c_2+2-k-b_i$
• $c_{b_i+1}\gets c_{b_i+1}-2$

当 $b_i+k\leq n+1$。此时对于后半段的影响不会在 $n$ 的右侧。

随便举个例子就可以发现，更新的位置就是 $c_{b_i+k+1}\gets c_{b_i+k+1}+1$。

当 $b_i+k> n+1$。此时对于后半段的影响会在 $n$ 的右侧。但我们只需要维护 $a_1\sim a_n$ 的变化，因此这部分完全不用分析。