「瑟班是我们的家乡，我不会让它落入孽物大军手中，」 —— 莎利雅 瑟班守护者莎利雅领导着一支护教军，这支护教军的兵力守卫在塞班的各个角落， 瑟班大教廷中有 n 个地点，编号为 1n1 sim n1n ，这 n 个地点排成一列，第 i 个地点有 di 的危险值，并有值为 fi 的兵力分布在这里， 为了更好的应战，每个地点所分布的兵力会根据每个地
「瑟班是我们的家乡，我不会让它落入孽物大军手中。」 —— 莎利雅 瑟班守护者莎利雅领导着一支护教军。这支护教军的兵力守卫在塞班的各个角落。 瑟班大教廷中有 n 个地点，编号为 1∼n1 sim n1∼n 。这 n 个地点排成一列，第 i 个地点有 di 的危险值，并有值为 fi 的兵力分布在这里。 为了更好的应战，每个地点所分布的兵力会根据每个地点危险值的变化而变化。更形式化地，第 i 个地点的兵力值 fi 可以根据以下公式计算： fi=max(di,min(maxj=1i−1dj,maxk=i+1ndk))f_i = max(d_i, min(max^{i-1}_{j=1} d_j, max^{n}_{k=i+1} d_k))fi=max(di,min(maxj=1i−1dj,maxk=i+1ndk)) 特别地，当 i=1 时，maxj=1i−1djdisplaystylemax^{i-1}_{j=1} d_jj=1maxi−1dj 项值为 0 ；当 i=n 时，maxk=i+1ndkdisplaystylemax^{n}_{k=i+1} d_kk=i+1maxndk 项值也为 0 。 现在，莎利雅作为瑟班的守护者、月主教护卫部队领袖，遇到了一些难题。她需要处理下级提供的情报，并能随时获取自己已分配的总兵力，或者了解哪些位置兵力足够、哪些位置兵力不足。 更形式化地，我们将这一系列操作分为以下三种： 1. 莎利雅需要知道已分配的总兵力：询问所有地点的兵力值总和。即 ∑i=1nfidisplaystyle sum_{i=1}^{n} f_ii=1∑nfi 。 2. 莎利雅需要知道某个区间内哪些位置兵力充足：编号在 [l, r] 的地点中兵力值大于等于 v 的个数。即 ∑i=lr[fi≥v]displaystyle sum_{i=l}^{r} [f_i ge v]i=l∑r[fi≥v]。 3. 莎利雅获得情报：地点 i 的危险值增加了 v 。由于乱战愈发激烈，每个地区的危险值不会降低。也就是说，v 是一个非负整数。 莎利雅正忙于跟莉莲娜维斯交战，所以只好请你来帮助她了！
