uniHk

分类

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

/ 注册

全部文章（共121篇）

Censoring (Gold)（AC自动机多字符串匹配+栈）

Censoring (Gold) 题意：给了一段文本串，再给了含 N N N个字符串的字典。将文本从左到右，如果遇到了字典中的字符串，则删...

2020-01-02

0 497

工艺（最小表示法）

工艺题意：给定长度为 n n n的序列，求字典序最小的长度为 n ...

2020-01-02

0 345

2-3-4 Tree

2-3-4 Tree 介绍 Conclusion 2-3-4 is great regarding memory and time complexity. Why isn’t it widely used? You may have noticed that while understand...

2020-01-02

0 603

Continuous Intervals（线段树+单调栈）

Continuous Intervals 线段树好题呀！比赛的时候根本看不出来，赛后惊叹“学到了！” 题意：给定一个数组，求数组内有多少连续区间。“连续区间”的定义：将区间内数字按大小排序后，相邻元素差值不大于1，可以等于0。思路：绝妙的思路！线段树+区间修改+区间最小值及最小值个数+单调栈 ...

2020-01-02

0 484

陌上花开（CDQ分治）

陌上花开第二遍写这个题了题意：若某个元素的三个维度的值都小于等于另外一个元素，则是真的小于等于；给出一些元素，求等级分别为 0 <mtext> <...

2020-01-02

0 468

天使玩偶（CDQ分治+最小曼哈顿距离）

天使玩偶题意：有两种操作：给二维平面上加入一个点询问二维平面上到某个点最近的一个点（用曼哈顿距离来表示）思路：标准的CDQ分治，离线处理两种操作当想到CDQ分治后本题的重点在于如何处理曼哈顿距离，毕竟看到绝对值都头疼我们最希望的是能去掉绝对值！这里有一种处...

2020-01-02

0 565

矩形藏宝地（CDQ分治+伪四维偏序）

矩形藏宝地这题虽然题面有种自相矛盾的感觉，但是样例还是清晰的，简单题题意：在一个二维平面上，求有多少个矩形是被包含在一个更大的矩形中的。思路：伪四维偏序由于题目竟然没有给出坐标的范围，因此我们拿到坐标还是离散化一下吧现将所有的矩形按照 ...

2020-01-02

0 425

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

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

2020-01-02

0 438

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

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

2020-01-02

0 466

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

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

2020-01-02

0 775