笛卡尔树

二叉树 搜索树性质+ 堆性质

在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。

上面是小根笛卡尔树

https://codeforces.com/contest/2048

F. Kevin and Math Class

a[n]

b[n]

目标 让所有ai=1, 求最小操作次数

每次操作选择l,r

令 x=min(b[l..r])

a[l..r]/=x (向上取整)

范围

2s

1024mb

n 2e5

ai [1,1e18]

bi [1,1e18]

我的思路

如果向下取整很常见，会注意到 顺序可换 x/a/b=x/b/a

那么向上取整，x in (kab,(k+1)ab], 同样是顺序可换

想法1.

如果最小的b 对应的a不是1,那么需要一次全区间

这样一些操作后，可以把a按照1的存在切割成多个块。没想到然后怎么用

想法2.

另一个是b=2的话，那么至少存在一个方案，每次全部操作，是log级别，所以 最优次数智慧更少，也没想到怎么用

想法3.

预处理，如果 相邻的 i,j=i+1有 ai >= aj, bi <= bj, 那么i每次操作带上j, 这样只要ai=1了那么aj必定等于1, 这样可以得到 相邻的a,b大小关系是一致的，也没啥用

想法4.

想贪心，用操作后的最大值来表示，但很快找到反例

• a=100 1 100
• b=100 2 100

这样 操作一次后的局部最优是 50 1 50, 而这无法达到最终的最少次数，

Dilworth 定理(偏序集分解定理)

关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。

偏序集能划分成的最少的全序集个数等于最大反链的元素个数。

对偶也是真: 任意有限偏序集,最长链元素的数目必等于最小反链划分中反链的数目

一些定义

原点集 = V

偏序( R 表示二元关系): 集合中一些元素可以比较大小

• 自反: A R A
• 反自反: A R B 且 B R A 则 A = B
• 传递: A R B 且 B R C 则 A R C

全序: 集合中元素两两可以比较大小

链: V的子集, 是全序集

反链(antichain): V的子集,其任意元素之间都不可以比较大小

链覆盖: 若干个链的并 = V, 且任意两个链不包含重复点

反链覆盖: 若干个反链的并 = V, 且任意两个反链不包含重复点

最长链: 所有链中点个数最多的链

最长反链: 所有反链中点个数最多的链

偏序集高度 = 最长链的点的个数

偏序集宽度 = 最长反链的点的个数

定理: 最小(链的数量最少)链覆盖个数 = 最长反链点的个数 = 偏序集宽度

最小(反链的数量最少)反链覆盖 = 最长链的元素个数 = 偏序集的深度

证明:

归纳法

对于点集$V$, 最大反链集合$A$

$d = |A|$

显然$A$的最小链覆盖 $\ge d$, (因为A中每个点覆盖的链一定两两不同, 其实要证的是等号)

若任何$V$的真子集(归纳更小的点数而不是更小的d)都满足 其最大反链集合大小=最小链覆盖

如果V中两两不可比较, 则 d = |V|, 正确性显然

如果 存在$A \neq \max(V)$, $V$中的最大元素构成的集合, 同时$A \neq \min(V)$, $V$中最小元素构成的集合

拆分$V$为 $A$ 和$\ge A$的集合$V_1$,$A$和$\le A$的集合$V_2$, (这里注意到$A$是最大反链意味着$V$中所有元素至少可以和$A$中的其中一个元素比较大小,所以这里才能拆分)

显然$V_1,V_2$的元素个数都比V小

A依然是$V_1,V_2$ 的最大反链集合, 因为首先不可能超过$A$, 否则同样的方案可以用在$V$上, 因此$A$是一个可达的上界

那么有$V_1,V_2$ 都是最小d个链覆盖, 且每个$A$中的被一条链覆盖, 这样靠着把V1,V2的链通过A中的点一一对应拼接上, 则依然是d条链覆盖, 所以是存在=d的方案

如果$A = \max(V)$

• 如果A中存在一个独立的不能和其它点比较的点$u$, 则$V - u$的最大反链 = $A - u$, 归纳得证
• 否则$A$中 每个点都存在更小的点和它能比较的点, $u\in \max(V)$ 使得 $V - u$ 的最大反链集合的$A_0$
  • 如果存在$|A_0|$元素个数依然是$d$, 则这个方案 也可以用在$V$中, 满足$A_0 \neq \max(V)$
    • 如果$A_0 \neq \min(V)$, 则满足第一种情况可证
    • 如果$A_0 = \min(V)$, 则考虑$A_0$中取一个能和$u$比较的点$v$, (V\u)\v
      • 如果这个最大反链集合$A_1$ 如果$|A_1|=d$, 则$A_1 \neq \max(V)$, $A_1 \neq \min(V)$, 满足第一种情况,可证
      • 否则$|A_1| = d-1$, 这里说明(V\u\v + [u,v]) 左边可以d-1条链覆盖，右边可以1条链覆盖，$\le d$ 和最开始的$\ge d$得到只能是$d$
  • $|A_0| = d-1$时, A\u 是一个$A_0$的方案, 说明$d-1$链能覆盖 V\u, 多加一个u 能覆盖V,得证

证毕

综上,归纳法有 最大反链集合的个数 = 最小链覆盖条数

相关

abc237Ex

abc354G

https://oi-wiki.org/math/order-theory/#dilworth-%E5%AE%9A%E7%90%86%E4%B8%8E-mirsky-%E5%AE%9A%E7%90%86

https://baike.baidu.com/item/%E7%8B%84%E5%B0%94%E6%B2%83%E6%96%AF%E5%AE%9A%E7%90%86/18900593

https://blog.csdn.net/qq_43408238/article/details/104542949

TLDR

有依赖关系的选择的问题，可以转化成 图论的最小割问题，再黑盒性质使用 最小割=最大流求出

project selection problem

https://codeforces.com/blog/entry/101354

流问题是算法竞赛的一个高级课题。 流问题的主要挑战往往不在于算法本身，而在于图的建模。 为了解决Project Selection Problem，我们将把它建模为最小切割问题的一个实例：”给你一个带加权边的有向图。 一个节点被指定为源节点，另一个节点被指定为汇节点。 删除一组总重量最小的边，使源点和汇点断开。 如果源点和汇点之间不再存在有向路径，则视为断开。 请注意，我们可以将最大流量问题视为一个黑盒子，它可以解决我们的最小切割问题。 因此，一旦我们设法将问题简化为最小切割，我们就可以认为问题已经解决。

Project Selection Problem 常见的形式

TL;DR;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

vector<int> euler_circuit(vector<vector<pair<int, int>>> G, int n/*点*/, int m/*边*/) { // 欧拉回路
    vector<int> path;
    vector<bool> used(m, false); // 边是否被使用
    function<void(int)> dfs=[&](int u) {
        for(auto [v,e]: G[u]) { // (点, 边)
            if(!used[e]) {
                used[e] = true;
                dfs(v);
            }
        }
        path.push_back(u);
    };
    dfs(0);
    reverse(path.begin(), path.end());
    return path;
}

直觉的数学证明

1. 所有点都是偶度

当我们对所有边至多访问一次进行dfs

那么对于非起始点u，dfs(u) 什么时候返回

1
2
3

dfs(u):
	for 未访问过的边edgeid，v : g[u]:
		dfs(v) <----- ?什么时候返回

直觉告诉我们，

1. 如果绕到了u的父节点来源 且无法dfs更深时会返回
2. 如果只是绕回了u,而u还有边是不会因此导致返回的

所以只有两种情况

1. 第一次返回 是 绕到更深无法继续，第二次是 绕回u且没有多的边
2. 只有一次 绕到更深无法继续

而发现 只要把顺序反过来就好了

相关

abc227H

https://codeforces.com/contest/1994/problem/F