四糸智乃

分类

算法(12) 题解(26)

/ 注册

TA的专栏 0篇文章 0人订阅

算法小入门

0篇文章 0人学习

全部文章（共2篇）

CDQ分治（基于归并排序的分治）

CDQ分治预备知识分治与传统分治相同，CDQ分治的核心思想也是分而治之。对于一个数组序列上的问题，分治的思想是总是考虑中的这一部分，而对于这一求解函数则使用递归表示。式子中的加号并不一定是加法，只表示答案的合并。这个说法有点过于抽象了。 ...

分治 CDQ分治

2020-10-10

25 4458

2019牛客多校第四场 C sequence

同南昌网络赛，贴过来改改直接过了。因为不单调，所以不能直接尺取，分治的话可以拿脚写。放宽了时限所以可以接受nlogn的复杂度。本来直接for是不单调的，但是如果规定分治中点mid，那么过mid往两侧延伸的最小值单调递减，过mid往两侧延伸的前缀和的前缀最大值与前缀最小值也是单调的。 ...

分治

2019-07-27

0 1019