网站首页
编程语言
数据库
系统相关
其他分享
编程问答
ARC166D
2024-07-14
AT_arc166_d [ARC166D] Interval Counts
我们可以将题转化为选择若干区间,给区间中的每个\(y_i\)减一,这样我们就可以将问题转化为差分了。我们枚举区间的左端点,从左到右枚举,当我们枚举到\(i\)时,显然如果当前差分数组\(d_i>0\),那么我们需要将其减去\(d_i\),这样我们获得了一个向后加总共\(d_i\)个\(1\)的机会,此时