【2018.10.20】noip模拟赛Day3 二阶和
今年BJ省选某题的弱化版……
这看起来就没那么难了,有几种方法维护,这里提两种。
第一种(傻逼的我写的)
维护 一维&二维前缀和。
对于一个长度为$m$的序列$b_1,b_2,...,b_m$,
由于 二维前缀和$=b_1*m+b_2*(m-1)+...+b_m*1$,
每一项都和$m$有关系,而$m$可以是任意子区间的长度,于是很不好维护。
我们可以解除这些数与$m$的关系,最简单的方法就是把它们反过来维护。
我们已经维护了一维前缀和(即$b_1 to b_m$的和),
所以我们可以反过来维护 $b_1*0+b_2*1+...+b_m*(m-1)$ 的和,二维前缀和就是$(b_1+b_2+...+b_m)*m-[b_1*0+b_2*1+...+b_m*(m-1)]$。
这样就有一个全局维护的方法能够解除每个数与$m$的直接关系,而只跟每个数本身的位置$-1$有关系,即线段树维护每个区间$[l,r]$的一维前缀和 $b_l+b_{l+1}+...+b_r$ 与二维前缀和 $b_l*(l-1)+b_2*l+...+b_m*(r-1)$。
然后我还写了对拍,包括最终测评数据在内,所有$n,m\le 5000$的数据都过了……我没理解啊……
因为测了大数据$n,m=100000$后我就WA上天了(基本上没有跟标答一致的输出)。
后来浪费时间查了好久,发现增加线段树上的二维前缀和时,求等差数列 $(l-1)+l+...+(r-1)$ 的和的通项公式中有个$÷2$,而除法不能随便取模(被除数和除数中任意组成部分都不能取模)……
应该是这么写 $((((ll)(l-1+r-1)*(r-l+1))>>1)\%mod)$
我是这么写的 $((((ll)(l-1+r-1)*(r-l+1)\%mod)>>1)$
数学没学好$=GG$
改完就差不多了吧。
也可以把除以$2$改成乘$2$的逆元,这样两边就可以随便取模了。$2$的逆元也比较简单,就是$\frac{mod+1}{2}$。
第二种(机房dalao们写的)
换一种反过来维护的方式。
我们考虑当一个数
最新文章
- Python帮助文档中Iteration iterator iterable 的理解
- 【转】MessageBox的常见用法
- mybatis新增数据后获取自增主键
- [Android Studio 权威教程]断点调试和高级调试
- ucenter实现原理
- oracle 11g 服务端下载地址及安装说明
- jquery的延迟加载插件Lazy Load Plugin for jQuery
- 《JavaScript 闯关记》之单体内置对象
- 使用hibernate 分表做增删改查
- BZOJ 2318: Spoj4060 game with probability Problem( 概率dp )
- MongoDB的全文检索(Text Search)功能
- UVA - 247 Calling Circles Floyd判圈
- Python模块 - time,datetime,calendar
- SpringBoot 中 get/post 请求处理方式,以及requestboy为Json时的处理
- Kilani and the Game-扩散形式的搜索
- VS 使用vs2017自带的诊断工具(Diagnostic Tools)诊断程序的内存问题
- 【数据结构】算法 LinkList (Insertion Sort List 链表插入排序)
- Windows环境手动DOS命令构建apk文件
- 输入系统:epoll &; inotify
- jquey中json字符串与json的转换(转)