本文从WordPress迁移而来, 查看全部WordPress迁移文章
树状数组
题意:题意很易懂就不说了吧,区间更新和区间查询。
关于这题的解法说法不一,有人说这种比较暴力的树状数组方法是水过去的,有人说不算。某牛用400ms就过了这题,但是他说可以证明,这种暴力的树状数组其实理论复杂度也是差不多的,跟用线段树是一样的。某牛400ms写的是线段树
树状数组做法很易理解
总区间是1到n,a[i]如果是lucky number那么就加1.查询[x,y]有多少lucky number,那么就是两个前缀和相减sum[y] - sum[x - 1].修改操作,如果一个a[i]从不是ln变成了ln,加1,从ln变成不是ln,减1
注意一开始的时候先预处理出1-100000这些数字哪些是ln,以后直接从标记数组中判断,否则在test 62中会超时
1 |
|