题解：支配点计数问题

题目理解

我们有一个点集 $(a_i, b_i)$，其中 $a$ 和 $b$ 都是 $1$ 到 $n$ 的排列。对于每个点 $i$，我们想知道有多少个排列 $p$ 使得在执行给定的伪代码后，最后保留的点是 $i$。

伪代码的逻辑是：遍历排列，如果当前点的两个坐标都大于等于已保存点的对应坐标，就更新保存的点。

问题转化

关键观察：一个点 $i$ 能够成为最后保存的点，当且仅当在排列中：

1. 点 $i$ 出现在所有能"支配"它的点之前（即所有 $a_j \geq a_i$ 且 $b_j \geq b_i$ 的点 $j \neq i$）
2. 点 $i$ 出现在所有它能支配的点之前（即所有 $a_j \leq a_i$ 且 $b_j \leq b_i$ 的点 $j \neq i$）

实际上，条件可以简化为：点 $i$ 必须是其"支配集合"中在排列里最早出现的点。

算法思路

1. 支配关系分析

对于点 $(a_i, b_i)$，定义：

• 被 $i$ 支配的点：满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 的所有点 $j$
• 支配 $i$ 的点：满足 $a_j \geq a_i$ 且 $b_j \geq b_i$ 的所有点 $j$

点 $i$ 能成为最后保存点的充要条件是：在排列中，$i$ 出现在所有支配它的其他点之前。

2. 概率与计数

设 $S_i$ 是支配点 $i$ 的点集（包括 $i$ 自身），大小为 $k_i$。

在随机排列中，点 $i$ 出现在 $S_i$ 中第一个的概率是 $\frac{1}{k_i}$。

因此，总排列中 $i$ 成为最后保存点的方案数为：

3. 特殊情况处理

但是有一个特殊情况：如果存在点 $j$ 严格支配 $i$（即 $a_j > a_i$ 且 $b_j > b_i$），那么 $i$ 永远不可能成为最后保存点，因为 $j$ 出现时会覆盖 $i$。

因此：

• 如果存在严格支配 $i$ 的点，则 $f_i = 0$
• 否则，$f_i = \frac{n!}{k_i}$，其中 $k_i$ 是支配 $i$ 的点数

代码解析

constexpr int MOD = 1000000007;
int fac = 1, n, a[100007], b[100007], pos[100007], f[100007];

// 快速幂求逆元
inline int qp(int a, int b, int t = 1) {
    for (; b; b >>= 1, a = a * a % MOD)
        if (b & 1)
            t = t * a % MOD;
    return t;
}

// 树状数组用于二维偏序计数
struct BIT {
    int data[100007];
    void add(int x, int k = 1) {
        for (; x <= n; x += x & -x) {
            data[x] += k;
            if (data[x] >= MOD) data[x] -= MOD;
        }
    }
    int sum(int x, int k = 0) {
        for (; x; x -= x & -x)
            k += data[x];
        return k % MOD;
    }
    int query(int l, int r) {
        return sum(r) - sum(l - 1);
    }
} tree;

主算法流程：

signed main() {
    cin >> n;
    
    // 计算 n!
    for (int i = 2; i <= n; i++)
        fac = fac * i % MOD;
    
    // 读入并建立映射
    for (int i = 1, x, y; i <= n; i++)
        cin >> x >> y, a[x] = y, pos[y] = i;
    
    // 第一遍树状数组：从后往前，计算每个点的支配者数量
    for (int i = n; i >= 1; i--) {
        b[i] = tree.query(a[i], n);  // 支配点i的点数
        tree.add(a[i]);
        b[i] = qp(b[i], MOD - 2);   // 存储逆元
    }
    
    // 第二遍树状数组：动态规划计算答案
    std::fill_n(tree.data, n + 1, 0);
    tree.add(1, qp(n, MOD - 2));  // 初始化
    
    for (int i = 1; i <= n; i++) {
        if (!b[i])  // 如果支配点数为0（实际上是被严格支配）
            f[pos[a[i]]] = tree.sum(a[i]) * fac % MOD;
        else
            tree.add(a[i] + 1, tree.sum(a[i]) * b[i] % MOD);
    }
    
    for (int i = 1; i <= n; i++)
        cout << f[i] << '\n';
    
    return 0;
}

关键技巧

1. 二维偏序处理

利用树状数组在 $O(n \log n)$ 时间内处理二维偏序关系。

2. 逆元计算

使用费马小定理和快速幂计算模逆元，避免除法。

3. 动态规划

通过巧妙的DP转移，在遍历过程中同时判断严格支配关系和计算方案数。

时间复杂度

• 预处理阶乘：$O(n)$
• 两遍树状数组操作：$O(n \log n)$
• 总体复杂度：$O(n \log n)$

算法标签

• 组合数学
• 二维偏序
• 树状数组
• 概率与期望
• 模逆元

总结

本题的核心在于理解支配关系和排列概率。通过二维偏序技术快速确定每个点的支配集合，然后利用组合数学计算符合条件的排列数。算法充分利用了 $a$ 和 $b$ 都是排列的性质，实现了 $O(n \log n)$ 的高效解法。