该如何快速高效地解决一维偏序问题

· · 算法·理论

建议点赞收藏，新手入门必看。

一维偏序怎么做？

给定序列 a，你需要回答对于 i \in [1,n]，a_j > a_i 的数量。

今天课上突然想到了这个问题，值得认真思考。

Solution 1

我们考虑分治。

我们可以先把 a 排序，这样更便于计算。

假设分治到 [l,r]，考虑计算跨过中点 mid 的贡献。

这样问题转化为对于 [l,r]，查询有多少个数 \ge x。

这是一个二维偏序问题，我们用离线扫描线来解决它。

时间是优秀的 O(n \log^2 n)。

Solution 1.1

鸣谢：感谢 @Mornstar 大佬提供的思路。

我们可以换一种思考方式，考虑最值分治，或者说笛卡尔树。

我们建出笛卡尔树，考虑如何计算贡献。

我们用线段树合并维护当前节点的值域线段树，然后每次计算跨过根节点的贡献，我们只需要 dsu on tree，对于小的子树计算大的子树有多少个 \ge x 的数。

这样就得到了一个 O(n \log^2 n) 的优秀做法。

Solution 2

问题是若干次查询有多少个数 \ge x，我们考虑莫队。

直接用树状数组是 O(n \sqrt n \log n)，我们考虑用值域分块平衡到 O(n \sqrt n)。

为了使复杂度得到保证，我们应该加入不计入答案的若干随机区间，以保证莫队的时间。

时间 O(n \sqrt n)。

Solution 3

让我们从图论的角度来考虑这个问题。

连边，当且仅当 a_i < a_j，就连 (i,j) 这条边。

可是，这样直接连边是 O(n^2) 的，我们该怎么优化捏？

这个时候，我们可以把 a 升序排序。

问题变成了要从 i 往一个区间 [l,r] 连边。

我们来一个全新的算法，考虑分块优化建图，每个整块建一个虚点往下面的散点连。

建完图然后再跑 Tarjan，记录每个点能到达的左端点，就可以解决这个问题了。

这样的时间复杂度就是 O(n \sqrt n) 的！！！

Solution 3.1

感谢 @yzq_yzq 提出。

我们按 Solution 3 的方式，同时做前缀优化建图。

缩点后，问题变成了 DAG 上的可达性统计。

这样就能在 O(\dfrac{n^2}{w}) 的时间解决这个问题。