何事秋。

数据结构基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 数据结构基本算法（共69篇）

单调队列：

O（n）一、ACwing 输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。输入格式第一行输入两个整数n,m。第二行输入n个数，代表长度为n的整数序列。同一行数之间用空格隔开。输出格式输出一个整数，代表该序列的最大子序和。数据范围...

2020-09-04

0 414

RMQ：

一、一维RMQ：前两天学lca的时候学了这个东西，今天再来系统的学一下。 P3865 【模板】ST表：题目背景这是一道ST表经典题——静态区间最大值请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) 题目描述给定一个长度为 N 的数列，和 M 次询问...

2020-09-04

0 300

哈夫曼树，哈夫曼编码：

一、哈夫曼树： ①、 P1090 合并果子：题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后，就只剩下...

2020-09-04

0 480

划分树：

话说这个东西大概要退出历史的舞台了吧。。。专用功能，静态查询区间第k大，主席树完全可以搞定啊，还能搞点别的。不过思想还是要学一下的。以下转自：https://blog.csdn.net/Akatsuki__Itachi/article/details/80030929 有这样一类题目，求的是区...

2020-09-04

0 548

分块：

分块大法好：具体应用见例题。一、A Simple Problem with Integers POJ - 3468： You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One ...

2020-09-04

0 395

线段树动态开点：

貌似权值线段树动态开点用的比较多。例题： I Hate It HDU - 1754 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更...

2020-09-04

0 474

权值线段树：

维护当前节点代表值出现的次数。题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1。插入x数 2。删除x数(若有多个相同的数，因只删除一个) 3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4。查询排名为x的数...

2020-09-04

0 595

线段树合并：

某一天马学长给我看了一个lca的题目，然而确实是lca+树上差分，但是仅仅有lca和树上差分解决不了，然后我就去面向题解编程了。可是这个线段树合并是个什么东东。。。然而今天看书，突然看到了这个线段树合并。就写一下了。 %mmh。 P4556 [Vani有约会]雨天的尾巴：题目背景深绘里一...

2020-09-04

0 447

离线分治算法：

一、基于时间的分治算法 --------CDQ分治例题：AcWing 254. 天使玩偶 Ayu在七年前曾经收到过一个天使玩偶，当时她把它当做时间囊埋在了地下。而七年后的今天，Ayu却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。我们把Ayu生活的小镇看做一个二维平面直...

2020-09-04

0 473

基环树：

把树再加一条边，形成一个环。处理基环树的方法，一般就是找出环，并且把环当成广义上的树根，处理树，然后处理环。一、AcWing 358. 岛屿：你准备有限一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一...

2020-09-04

0 350