是否有数据结构(或者别的什么东西)可以做这个东西:
给定两个长为 nnn 的序列 A,BA,BA,B,支持以下两个操作:
∀ i∈[1,n],Ai←Ai+Bi\forall \,i\in[1,n],A_i\gets A_i + B_i∀i∈[1,n],Ai←Ai+Bi。
∀ i∈[1,n],Ai=minj=1iAj\forall \,i\in[1,n], A_i=\min\limits_{j=1}^iA_j∀i∈[1,n],Ai=j=1miniAj
在所有操作结束后输出 AAA。
n≤105n\le 10^5n≤105。
也就是全局加恒定数列,从前往后做前缀 min\minmin。