分块、树状数组 题意： 因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：给定一个长度为N的序列A，所有元素初值为0。接下来有M次操作或询问：操作：输入
展开全文
直接for（int i=x;i<=n;i+=x）add(i,y)；最坏是o(n^m)=1e10，会爆掉所以需要用个lazy[]进行分块统计小于sqrt(n)复杂度较大的那一部分y，最后在算range_sum(x,y)的时候加上[x,y]中lazy[]数组的贡献 #pragma GCC opti
展开全文
当d<=sqrt(n)时 直接暴力修改树状数组的值会使复杂度退化到O(n²)所以这里要用到分块的思想，修改lazy标记lazy[i]表示i的倍数的位置中所有的数组成的一个块，查询时l到r对应的lazy，这中间有r/i-(l-1)/i个数，乘以lazy[i]就是分块记录的答案跟树状数组直接记录的
展开全文
思路：分块，树状数组直接树状数组进行add操作for(int i=d;i<=n;i+=d))add(d,k)时间复杂度起码是O(n^m^)=1e10，肯定t这个时候我们可以考虑进行分块操作对于d小于等于√n的我们就存到一个lazy数组里大于√n的我们就直接进行树状数组的add操作这样的话根据上
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
