主席树总结

简述

主席树是一个很有意思的数据结构,其全称其实是「可持久化线段树」,至于为什么叫「主席树」是因为:

由于发明者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛(H.J.T.)相同,因此这种数据结构也可被称为总书记树或主席树。

From Wikipedia.org

继续阅读主席树总结

单调队列学习笔记

简单的问题引入

例题:CH1201

输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。

以前写的题解:CH1201:最大子序和题解

首先思考暴力:枚举端点和不大于\(m\)的长度,前缀和搞一搞就好,时间复杂度为\(O(n^2)\),肯定超时。我们可以考虑优化这个算法。

继续阅读单调队列学习笔记