本文从WordPress迁移而来, 查看全部WordPress迁移文章
【UVA提交失败,至今还没有评判】
线段树 区间更新 区间求和(有点特殊)
题意:给出长度为n的区间,一开始每个单元的权值为100,有查询和修改操作。修改操作时一个区间内每个单元的权值都加上一个D;查询操作时查询一个区间内的和,不过不是简单相加,而是每个单元附一个权值:
查询[L,R]权值和 = 1 v[L] + 2 v[L+1] + 3 v[L+2] + …….. + (L+R) v[R]
对于查询我是这样做的,将要查询的区间分成多段,每一段内,该段里面的每个单元的权值是相同的,那么该段的权值和就可以直接算出,例如
[5,15], [5,7]每个单元的权值都是100,[8,13]每个单元的权值都是200,[14,15]每个单元的权值都是150
那么整个区间的和 = (1+2+3) 100 + (4+5+6+7+8+9) 20 + (10+11) * 150,这样就只计算了3次
因为最悲剧的情况就是整个区间内每个单元的权值都是不同的,那么相当于一个一个单元累加起来
可惜UVA还不能提交不知道是否能通过,先做一个记录
1 |
|