搜索结果
查询Tags标签： 偏序，共有 22条记录-
洛谷 P3810 【模板】三维偏序（陌上花开）
原题链接 第一维直接排序，然后cdq分治+树状数组 对于分治的左右区间，区间内部按照第二维排序（已按第一维排序好了，就算打乱顺序，左右区间整体的第一维的偏序关系也不会受到影响） 然后遍历右区间的元素，把左区间的第二维小于当前元素的加入树状数组，统计答案即可，…
2022/9/10 6:55:35 人评论 次浏览 -
cdq分治
cdq分治，一种广为人知的离线分治算法。大体的思想是：将左右两边区间分开递归处理。 统计左边区间修改对右边区间查询的影响。第一步很简单，写两个递归就行了。关键在第二步。我们搞个cdq的经典问题——三维偏序来具体解释这个东西。 P3810 【模板】三维偏序（陌上花开）…
2022/9/3 23:22:59 人评论 次浏览 -
模拟赛 矩形 （扫描线，三维偏序，线段树合并，并查集，线段树上二分）
PRO 题目大意：给定$N$个矩形，求连通块个数。($1 \leq N,x_1,x_2,y_1,y_2 \leq 100000$) SOL 乍一看就能知道是扫描线，不过这题的细节恐怖的要命。 （std同样看不懂，自己魔改了一下） 首先把完全相同的矩形去掉。 之后咱们可以发现，被其他矩形完全包含的小矩形对答案没…
2022/8/29 6:24:02 人评论 次浏览 -
【题解】 洛谷 P1631 序列合并
这个题提供给了我们一个比较新颖的思考方向： 发现由所有的和可以组成这样的 \(n\) 个偏序集： \[\{a_1+b_1,a_1+b_2 \dots a_1+b_n\} \]\[\{a_2+b_1,a_2+b_2 \dots a_2+b_n\} \]\[\dots \]\[\{a_n+b_1,a_n+b_2 \dots a_n+b_n\} \]然后我们可以考虑把每个偏序集中最小的…
2022/7/23 23:26:41 人评论 次浏览 -
全序和偏序的关系
偏序关系是全序关系的子集，某集合上的一个全序关系一定是一个偏序关系，反之这不一定成立。 偏序关系满足自反、反对称、传递，而全序关系多了一个total，我的理解就是，集合中任意两元素都具有该关系，如≥、≤就是全序关系。 全序是指，集合中的任意两元素之间可以进行…
2022/6/15 23:22:41 人评论 次浏览 -
cdq分治&整体二分 学习笔记
我只是个萌新，写一篇学习笔记，希望可以帮助未来的自己和他人。如果有大佬看到了错误，您可以在评论区或者私信中指出，并且我非常欢迎您的纠错。本博客还是从二维偏序开始铺垫，对cdq分治进行讲解（实际上是给自己讲，因为没人看）。 前置知识：归并排序 cdq分治的学习需…
2022/2/24 23:28:20 人评论 次浏览 -
广度优先搜索— —提高Ⅰ
CDQ分治 CDQ分治，传说中是一个神犇创造的算法。 在了解这种算法之前，我们有必要了解一下一种基本的思想：分治。 分治介绍 分而治之，将原问题不断划分成若干个子问题，直到子问题规模小到足以直接解决 子问题间互相独立且原问题形式相同，递归求解这些子问题，然后将各…
2022/2/11 23:16:50 人评论 次浏览 -
CDQ分治（初步入门）
CDQ分治 CDQ分治，传说中是一个神犇创造的算法。 在了解这种算法之前，我们有必要了解一下一种基本的思想：分治。 分治介绍 分而治之，将原问题不断划分成若干个子问题，直到子问题规模小到足以直接解决 子问题间互相独立且原问题形式相同，递归求解这些子问题，然后将各…
2022/2/11 23:16:27 人评论 次浏览 -
[省选集训2022] 守序划分问题
一、题目 将 \(\{1,2,3...n\}\) 划分成 \(m\) 个组，每组中至少有一个数，记为 \(a_1,a_2...a_m\) 称一个划分是"好的"，当且仅当存在排列 \(p_1,p_2...p_m\)，令 \(p_0=p_m\) 则有 \(\max(a_{p_i})>\min(a_{p_{i-1}})(1\leq i\leq m)\) 两个划分本质不同，当…
2022/1/13 23:37:29 人评论 次浏览 -
[省选集训2022] 守序划分问题
一、题目 将 \(\{1,2,3...n\}\) 划分成 \(m\) 个组，每组中至少有一个数，记为 \(a_1,a_2...a_m\) 称一个划分是"好的"，当且仅当存在排列 \(p_1,p_2...p_m\)，令 \(p_0=p_m\) 则有 \(\max(a_{p_i})>\min(a_{p_{i-1}})(1\leq i\leq m)\) 两个划分本质不同，当…
2022/1/13 23:37:29 人评论 次浏览 -
HNOI2022 树上问题
考点基环树 树链剖分 树上DP 树上分治点分治NOTE 1.分治前求dep的时候忘记dep[rt]=0流程1(适用于计数等容易去重的)找根 处理过当前根到子树内的路径(加入根到根的路径，用两条到根的路径合并) 去掉不合法(统计同一个子树出来到当前根的两条路径)，继续分治流程2(适用于最…
2021/12/17 23:28:45 人评论 次浏览 -
HNOI2022 树上问题
考点基环树 树链剖分 树上DP 树上分治点分治NOTE 1.分治前求dep的时候忘记dep[rt]=0流程1(适用于计数等容易去重的)找根 处理过当前根到子树内的路径(加入根到根的路径，用两条到根的路径合并) 去掉不合法(统计同一个子树出来到当前根的两条路径)，继续分治流程2(适用于最…
2021/12/17 23:28:45 人评论 次浏览 -
HDU6943_二维树状数组解决三维偏序问题
传送门 题意 给定一个 \(N \times M\) 的矩阵 \(A\)，规定：点 \((x_{1}, y_{1})\) 控制 \((x_{2}, y_{2})\) 当且仅当 \(A[x_1][y_1] > A[x_2][y_2] + |x_1-x_2| + |y_1-y_2|\) 问满足上述控制条件的有序对 \(((x_1,y_1),(x_2,y_2))\) 的个数 \(N, M \le 10^3, 1 \le …
2021/11/4 6:09:41 人评论 次浏览 -
HDU6943_二维树状数组解决三维偏序问题
传送门 题意 给定一个 \(N \times M\) 的矩阵 \(A\)，规定：点 \((x_{1}, y_{1})\) 控制 \((x_{2}, y_{2})\) 当且仅当 \(A[x_1][y_1] > A[x_2][y_2] + |x_1-x_2| + |y_1-y_2|\) 问满足上述控制条件的有序对 \(((x_1,y_1),(x_2,y_2))\) 的个数 \(N, M \le 10^3, 1 \le …
2021/11/4 6:09:41 人评论 次浏览 -
关于偏序问题
二维偏序问题，可以用排序+树状数组实现 多维呢，我们发现有bitset压位（not paratical） kdt（利用分治，常数极大） 二进制分组主席树 区间修改主席树（空间极大） 树套树（空间极大），又分为多种树套多种树 cdq分治，常数极小，只能离线 整体二分，在特殊情况下只能用…
2021/10/4 23:13:27 人评论 次浏览
