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

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

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

我们考虑分治。

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

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

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

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

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

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

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

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

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

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

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

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

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

时间 $O(n \sqrt n)$。

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

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

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

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

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

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

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

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

感谢 @yzq_yzq 提出。

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

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

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