埃兰希尔

题解

线段树(1)

/ 注册

全部文章 / 题解（共7篇）

线段树合并模拟

节选自我的博客 NC15557 连续区间的最大公约数这道题没有修改，只有查询。查询最大公约数还是比较简单的，但是查询子区间的最大公约数也等于整个区间的最大公约数的数量，这就不这么快乐了。假设我们两个孩子区间的和他们子区间满足条件的数目，要合并成父亲区间，父亲区间的就是对两孩子...

线段树

2020-08-05

2 550

线段树合并模拟

节选自我的博客牛客网：NC20279 [SCOI2010]序列操作洛谷：P2572 [SCOI2010]序列操作牛客做的人比较少，建议在洛谷上做。 3个操作，2个查询，线段树模拟大题。来想一想要维护什么信息。首先，和在这道题中反复转换，所以每种信息肯定给和分别维护一...

线段树

2020-08-05

2 476

线段树差分和最大公约数

更好的阅读体验简述概念和应用所谓的差分，其实就是后一项与前一项的差，对于第一项而言，。设数组，那么差分数组，即 ,那么， NC26255 小阳的贝壳这题要求最大公因数和差分最值，最值上一题已经求过了，这最大公因数怎么维护出来呢？而且修改是区间修改的，这貌似也增加了...

线段树

2020-08-04

3 612

线段树差分

更好的阅读体验简述概念和应用所谓的差分，其实就是后一项与前一项的差，对于第一项而言，。设数组，那么差分数组，即 ,那么，差分在线段树和树状数组上应用很广泛。关于树状数组的差分可以用来解决“区间修改，单点查询”的问题，在我上一篇博客讲树状数组入门时有分析，题目是P336...

线段树

2020-08-04

7 814

线段树RMQ问题

听说博客观看效果更佳这道题是比较经典的问题,找到X和Y年间的最值来进行判断真假 , 用线段树维护是比较简单好写的。然而这只是一个小判断，比较难的是判断。如果没有想好直接打代码会调很久（没错就是我）。怎么维护查询区间最大值我就不再这里赘述了，不懂线段树的先去入门（此题也是线段树入门...

线段树

2020-07-31

1 529

中国剩余定理(CRT)及其扩展(EXCRT)详解

中国剩余定理(CRT)及其扩展(EXCRT)详解博客园食用效果更佳问题背景孙子定理是中国古代求解一次同余式方程组的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如...

扩展欧几里得算法中国剩余定理数论

2020-07-24

21 2394

Miller-Rabin素数测试算法

Miller-Rabin素数测试算法博客园食用效果更佳哦用来干嘛的要判断一个数是否为素数，最朴素直接的办法是以时间复杂度地从2到循环即可得到最准确的结果。但是如果在比较大的情况下，时间花销就太大了。这时，我们可以选择牺牲一点点准确度，使用可爱的米勒-拉宾（Miller-...

数论质数

2020-07-23

8 2226