wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

算法基础

二维偏序

高维前缀和

[[ item.c ]]

二维偏序

## 二维偏序问题
二维偏序问题在算法竞赛中非常常见，下面以一个例子来说明
**[2025 杭电多校 半](https://acm.hdu.edu.cn/contest/problem?cid=1173&pid=1006)**
给定两个排列`a, b`，分别表示不同人，在`a, b`两场比赛中的名次，现在要你回答$$i \in [1, n]$$
表示说轮到第`i`个选手，它可以禁赛若干人，问他要禁赛多少人，才能保证他在**两场比赛中都拿第一**

**算法分析**
实际上，对于选手$$x$$，他在`a, b`两场比赛中的位次分别是$$pa, pb$$
如果前面没有**重复的选手**，答案就是$$(pa-1) + (pb-1)$$

但问题是，有若干重复的选手，我们用`posa, posb`分别表示选手在`a, b`两场比赛中的名次
什么样的选手会重复呢？
```math
\displaystyle
\begin{cases}
posa(y) \leqslant pa \\
posb(y) \leqslant pb
\end{cases}
```
所有满足以上条件的$$y \in [1, n]$$选手都是会重复的，我们要统计这样的点的数量
实际上就是一个**二维偏序问题**

> 二维偏序问题解决思路

1.按照$$pa$$为**第一关键字**，对每个点进行排序
2.按$$pa$$从小到大，用**树状数组**维护每个点，因为你是从小到大加点的，所以被加入的点天然满足$$pos \leqslant pa$$的
你只需要考虑$$\leqslant pb$$有多少个即可，**单点修改，查询都只需要考虑`pb`这一维**
3.先查询，`let del = tr.sum(pb)`，更新答案；然后考虑`tr.add(pb, 1)`

**算法实现**
```bash
void solve(int cas) {
    int n;
    cin >> n;

vector<int> a(n+1, 0), b(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

vector<int> posa(n+1, 0), posb(n+1, 0);
    for (int i = 1; i <= n; i++) posa[ a[i] ] = i;
    for (int i = 1; i <= n; i++) posb[ b[i] ] = i;

using pint = pair<int, int>;
    vector<pint> vec;
    for (int x = 1; x <= n; x++) vec.emplace_back(posa[x], posb[x]);
    sort(vec.begin(), vec.end());
    
    Fenwick<int> tr(n);

vector<int> ans(n+1, 0);
    for (auto [pa, pb] : vec) {
        auto x = a[pa];
        int tot = pa - 1 + pb - 1;
        int del = tr.sum(pb);

ans[x] = tot - del;

tr.add(pb, 1);
    }

for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << "\n";
}
```

## 二维数点
**[区间不同数之和](https://ac.nowcoder.com/acm/contest/1084/B)**
**问题描述**
给定一个长度为$$n$$的序列，若干询问，每次询问回答**区间和**$$[l, r]$$，如果一个数出现多次，只算一次

**算法分析**
我们计$$pre(i)$$表示$$a_i$$上一次出现的位置，实际上这就是统计
```math
\displaystyle
\begin{cases}
pre(i) \leqslant l-1 \\
l \leqslant i \leqslant r
\end{cases}
```
这是一个关于$$(i, pre(i))$$的**二维数点**问题

将点分为`原有点，查询点`
```bash
原有点 (x, 点的类型, y, 值)
查询点 (x, 点的类型, y, 询问编号)
```
执行询问$$(r, l-1) - (l-1, l-1)$$，把它们都封装成事件，按照$$x$$作为第一关键字排序
下面只需要考虑**`y`这个维度的单点修改和查询**

```bash
用全局变量 ans 维护答案

遇到原有点 (x, 0, y, val)
树状数组单点增加，tr.add(y, add)

遇到查询点，当前查询的值是 res = tr.sum(y)
如果点的类型 = 2, ans += res
如果点的类型 = 1, ans -= res
```

因为加减操作无所谓顺序，所以只要遍历`evts`到相应的位置，该加的都加上，该减的都减去
这样就可以得到答案

**算法实现**

```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

vector<i64> a(n+1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    auto MX = *max_element(a.begin(), a.end());

using arr = array<i64, 4>;

vector<i64> pre(n+1, 0), last(MX+1, 0);
    for (int i = 1; i <= n; i++) {
        auto x = a[i];

pre[i] = last[x];
        last[x] = i;
    }

vector<arr> evts;
    for (int i = 1; i <= n; i++) {
        auto x = 1LL * i, y = pre[i];
        evts.push_back(arr{x, 0, y, a[i]});
    }

for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        evts.push_back(arr{r, 2, l-1, i}), evts.push_back(arr{l-1, 1, l-1, i});
    }

sort(evts.begin(), evts.end());
    Fenwick<i64> tr(n+5);

vector<i64> ans(m+5, 0);

for (auto [x, tp, y, d] : evts) {
        if (tp == 0) {
            tr.add(y+1, d);
        }
        else {
            auto &res = ans[d];
            i64 S = tr.sum(y+1);

tp == 2 ? (res += S) : (res -= S);
        }
    }

for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
}
```

> 总结，二维数点的本质也是二维偏序问题

对于$$x$$这个维度，$$l \leqslant x \leqslant r$$转化成$$(x \leqslant r) - (x \leqslant l-1)$$
我们统计$$x \leqslant l-1$$，按$$x$$从小到大排序，考虑到$$l_i - 1$$这个点的时候
树状数组中的点，$$x$$这一维都是天然$$\leqslant l_i - 1$$的，只需要查询$$y$$有多少个满足约束即可

只不过这个问题带了符号，如果是`-(l-1)`，那么对答案的贡献是`-tr.sum(y)`而已

看完文章有啥想法

算法小站

wiki 主题

算法基础

二维偏序

目录