uniHk

CDQ分治

01Trie(5) AC自动机(7) 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)

/ 注册

全部文章 / CDQ分治（共4篇）

陌上花开（CDQ分治）

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

2020-01-02

0 468

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

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

2020-01-02

0 565

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

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

2020-01-02

0 426

动态逆序对（CQOI）（CDQ分治 or 主席树）

动态逆序对（重庆OI）先写一个CDQ分治的写法吧，主席树。。。希望我以后会补。题意：先给定一个 1 1 1~ ...

2020-01-02

0 503