uniHk

主席树

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / 主席树（共5篇）

主席树

主席树小小总结： 1. 主席树静态区间第k小板子 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back...

2020-01-02

0 406

粟粟的书架（主席树+二维前缀和）

粟粟的书架一下子做了两个题？题意：一个问题求区间前K大的和，另一个问题求矩形内前K大的和。思路：前一个问题直接上主席树+二分搞定后一个问题由于数据范围比较小，用 c ...

2020-01-02

0 439

森林（树上主席树+启发式合并）

森林题意：有两种操作： 1. 将某两个点连起来（连边后保证为森林或者一棵树） 2. 询问两点之间路径上第K小权值（强制在线且保证询问合法）思路：树上主席树+启发式合并先离散化一下还是有必要的连边后分别在每一棵树上建立主席树，每一棵树上的每一个节点的主席树维护从所在的树根到当前节...

2020-01-02

0 468

任务查询系统（主席树的差分性质）

任务查询系统题意：区间修改（修改区间每个位置某个数的数量，注意每个位置有多个数）+单点查询前K小的权值和+强制在线思路：由于主席树运用了前缀和思想，每个位置保存了所有权值的前缀和；因此若此题的区间修改利用差分思想，则主席树的每个位置恰好就维护的是自身位置（差分与前缀和相互抵消了），...

2020-01-02

0 775

超级钢琴（主席树+贪心+优先队列）

超级钢琴我能说这是主席树板子题嘛？题意：给定一个序列，求长度在 L L L与 ...

2020-01-02

0 417