Absoler

模板

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 真题(9) 计算几何(1)

/ 注册

全部文章 / 模板（共3篇）

线段树RMQ(MAX)模板

const int MAX_N=300010; int dat[2*MAX_N-1]; int n; #define maxn 0x3f3f3f3f void init(int _n){ n=1; while(n<_n) n<<=1; fo...

2020-05-09

0 532

扫描线+离散化+线段树HDU1255&POJ1177

首先我们要对扫描线算法建立一个形象的认识，可以参考链接。大概就是，对于某个由多个矩形覆盖重叠形成的不规则几何体的面积，可以转化为从下往上一系列小矩形，有点像垒砖，层数为线段数-1，也就是矩形数*2-1。在这个算法里，线段树维护整个区间被覆盖的，有效的“长”，它是由一小段一小段的线段组成，我们对于...

2020-05-09

0 563

可持久化线段树

可持久化线段树可以用来解决这个经典问题：对于给定数字序列，求出 [l, r] 区间中第K大的数。我们首先考虑这样一棵线段树i，它的每个节点对应一段值域，记录了数组中[1, i]区间中的数字有多少落在这个值域。如果我们能有n棵这样的线段树，那么对于区间第K大问题就可以通过搜索来解决，这...

2020-05-09

0 854