埃兰希尔
埃兰希尔
全部文章
分类
线段树(1)
题解(7)
归档
标签
去牛客网
登录
/
注册
埃兰希尔的博客
全部文章
(共8篇)
线段树合并模拟
节选自我的博客 NC15557 连续区间的最大公约数 这道题没有修改,只有查询。查询最大公约数还是比较简单的,但是查询子区间的最大公约数也等于整个区间的最大公约数的数量,这就不这么快乐了。假设我们两个孩子区间的 和 他们子区间满足条件的数目 ,要合并成父亲区间,父亲区间的 就是对两孩子...
线段树
2020-08-05
3
714
线段树合并模拟
节选自我的博客 牛客网 :NC20279 [SCOI2010]序列操作 洛谷 :P2572 [SCOI2010]序列操作 牛客做的人比较少,建议在洛谷上做。 3个操作,2个查询,线段树模拟大题。来想一想要维护什么信息。首先, 和 在这道题中反复转换,所以每种信息肯定给 和 分别维护一...
线段树
2020-08-05
2
594
线段树差分和最大公约数
更好的阅读体验 简述概念和应用 所谓的差分,其实就是后一项与前一项的差,对于第一项而言, 。设数组 ,那么差分数组 ,即 ,那么, NC26255 小阳的贝壳 这题要求最大公因数和差分最值,最值上一题已经求过了,这最大公因数怎么维护出来呢?而且修改是区间修改的,这貌似也增加了...
线段树
2020-08-04
3
828
线段树差分
更好的阅读体验 简述概念和应用 所谓的差分,其实就是后一项与前一项的差,对于第一项而言, 。设数组 ,那么差分数组 ,即 ,那么, 差分在线段树和树状数组上应用很广泛。关于树状数组的差分可以用来解决“区间修改,单点查询”的问题,在我上一篇博客讲树状数组入门时有分析,题目是P336...
线段树
2020-08-04
7
1002
线段树和树状数组学习笔记
更好的阅读体验 学习了一周的线段树和树状数组,深深地体会到了这每种操作几乎都是 级别的数据结构的美,但是做起题来还是相当痛苦的(特别是一开始只会模板的时候,很难灵活运用线段树的性质)。还好有雨巨大神带入门,视频讲解十分直观(b站上也有很多介绍线段树的视频),不用像以前一样看各种博客题解入...
树状数组
线段树
2020-08-02
0
783
线段树RMQ问题
听说博客观看效果更佳 这道题是比较经典的 问题,找到X和Y年间的最值来进行判断真假 , 用线段树维护是比较简单好写的。然而这只是一个小判断,比较难的是判断 。如果没有想好直接打代码会调很久(没错就是我)。怎么维护查询区间最大值我就不再这里赘述了,不懂线段树的先去入门(此题也是线段树入门...
线段树
2020-07-31
1
658
中国剩余定理(CRT)及其扩展(EXCRT)详解
中国剩余定理(CRT)及其扩展(EXCRT)详解 博客园食用效果更佳 问题背景 孙子定理是中国古代求解一次同余式方程组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如...
扩展欧几里得算法
中国剩余定理
数论
2020-07-24
23
2960
Miller-Rabin素数测试算法
Miller-Rabin素数测试算法 博客园食用效果更佳哦 用来干嘛的 要判断一个数 是否为素数,最朴素直接的办法是以 时间复杂度地从2到 循环即可得到最准确的结果。但是如果在 比较大的情况下,时间花销就太大了。这时,我们可以选择牺牲一点点准确度,使用可爱的米勒-拉宾(Miller-...
数论
质数
2020-07-23
8
2527