3140. 「COI 2019」TENIS 详细题解（线段树优化版）

算法优化思路

朴素算法的瓶颈

朴素做法的时间复杂度为 $O(QN)$，每次查询都要遍历所有选手，在极端情况下可能超时。

这个优化算法通过线段树维护关键信息，将查询复杂度降低到 $O(\log N)$。

---

核心数学思想

关键观察 1：排名跨度

对于选手 $x$，定义：

• 最好排名：$\text{best}[x] = \min(q[0][x], q[1][x], q[2][x])$
• 最差排名：$\text{worst}[x] = \max(q[0][x], q[1][x], q[2][x])$
• 排名跨度：区间 $[\text{best}[x], \text{worst}[x]]$

数学意义： 选手 $x$ 的排名在三个场地上"分布"在这个跨度内。

关键观察 2：支配关系的等价条件

定理： 选手 $y$ 能在所有场地战胜选手 $z$，当且仅当：

$$\text{worst}[y] < \text{best}[z]$$

证明：

• $\Rightarrow$：如果 $y$ 在所有场地都比 $z$ 强，则：

  $$\max(q[0][y], q[1][y], q[2][y]) < \min(q[0][z], q[1][z], q[2][z]) $$

  即 $\text{worst}[y] < \text{best}[z]$

• $\Leftarrow$：如果 $\text{worst}[y] < \text{best}[z]$，则对于任意场地 $i$：

  $$q[i][y] \leq \text{worst}[y] < \text{best}[z] \leq q[i][z] $$

  因此 $y$ 在所有场地都强于 $z$

关键观察 3：覆盖区间

定义选手 $x$ 覆盖区间 $[\text{best}[x], \text{worst}[x] - 1]$。

重要性质： 如果排名位置 $r$ 被选手 $x$ 覆盖（即 $\text{best}[x] \leq r < \text{worst}[x]$），则：

• 选手 $x$ 至少在一个场地的排名 $\leq r$
• 选手 $x$ 至少在一个场地的排名 $> r$
• 含义： 排名在 $r$ 的选手无法在所有场地都战胜 $x$

---

算法核心：临界点

临界点定义

设 $\text{pos}$ 为最小的未被任何选手覆盖的排名位置。

临界点的数学意义

引理： 选手 $y$ 能夺冠 $\Leftrightarrow$ $\text{worst}[y] \leq \text{pos}$

证明：

充分性（$\text{worst}[y] \leq \text{pos}$ $\Rightarrow$ $y$ 能夺冠）：

反证法。假设存在选手 $z$ 在所有场地都比 $y$ 强，则：

$$\text{worst}[z] < \text{best}[y] \leq \text{worst}[y] \leq \text{pos} $$

因此 $\text{worst}[z] < \text{pos}$。

考虑排名位置 $r = \text{worst}[z]$：

• 由于 $r < \text{pos}$，根据 $\text{pos}$ 的定义，$r$ 必定被某个选手覆盖
• 设选手 $x$ 覆盖了 $r$，即 $\text{best}[x] \leq r < \text{worst}[x]$
• 则 $\text{best}[x] \leq \text{worst}[z]$

分析 $x$ 和 $z$ 的关系：

• $\text{worst}[z] \geq \text{best}[x]$ 意味着 $\max(q[i][z]) \geq \min(q[j][x])$
• 因此至少在一个场地上，$z$ 的排名 $\geq$ $x$ 在某个场地的排名
• 核心： 这意味着 $z$ 不能在所有场地都比 $x$ 强

由于 $\text{worst}[z] < \text{best}[y]$，我们知道 $z$ 在所有场地都比 $y$ 强，因此 $z$ 的排名都非常靠前。但 $z$ 无法在所有场地都比 $x$ 强，这说明 $x$ 至少在一个场地上比 $z$ 强或相当。

实际上，这个证明的关键在于：

• 如果 $\text{worst}[y] \leq \text{pos}$，说明所有排名 $< \text{pos}$ 的位置都被覆盖
• 任何试图"完全支配" $y$ 的选手 $z$，其 $\text{worst}[z] < \text{best}[y] \leq \text{pos}$
• 但由于覆盖性质，这样的 $z$ 必定被其他选手在某个场地上"突破"
• 因此不存在能完全支配所有人的选手链条

必要性（$y$ 能夺冠 $\Rightarrow$ $\text{worst}[y] \leq \text{pos}$）：

反证法。假设 $\text{worst}[y] > \text{pos}$。

由于 $\text{pos}$ 是最小未被覆盖的位置，考虑区间 $[\text{pos}, \text{worst}[y] - 1]$：

• 这个区间内的所有位置都未被任何选手覆盖
• 这意味着所有选手 $x$ 都满足：要么 $\text{worst}[x] \leq \text{pos}$，要么 $\text{best}[x] \geq \text{worst}[y]$

构造选手集合 $A = \{x : \text{worst}[x] < \text{pos}\}$：

• 对于 $x \in A$，有 $\text{worst}[x] < \text{pos} \leq \text{best}[y]$（因为 $\text{pos}$ 未被覆盖）
• 因此集合 $A$ 中的所有选手在所有场地都比 $y$ 强
• 特别地，如果 $A$ 非空，则 $y$ 不能夺冠

由于 $y$ 能夺冠，所以 $A$ 必须为空，即不存在 $\text{worst}[x] < \text{pos}$ 的选手。但这与 $\text{pos}$ 的定义矛盾（$\text{pos}$ 是最小的未被覆盖位置，说明 $\text{pos} - 1$ 被覆盖，因此存在选手 $x$ 使得 $\text{worst}[x] > \text{pos} - 1$，即 $\text{worst}[x] \geq \text{pos}$）。

实际上，更直观的理解是：

• $\text{pos}$ 划分了一个"分界线"
• 排名 $\leq \text{pos}$ 的选手们"互相制衡"，没有人能完全支配所有人
• 排名 $> \text{pos}$ 的选手必定被某些 $\leq \text{pos}$ 的选手完全支配

---

数据结构设计

线段树节点定义

struct node {
    int flg;   // 当前区间被覆盖的次数（差分标记）
    int pos;   // 当前区间内最小的未被覆盖位置（0表示全被覆盖）
    int l, r;  // 区间左右端点
};

核心操作

1. 区间修改 add(x, y, z, w)

在区间 $[y, z]$ 上增加 $w$ 次覆盖（$w$ 可以是 $\pm 1$）。

void add(int x, int y, int z, int w) {
    if (t[x].l == y && t[x].r == z) {
        t[x].flg += w;  // 更新覆盖次数
        
        if (t[x].l == t[x].r) {
            // 叶子节点
            if (t[x].flg) 
                t[x].pos = 0;      // 被覆盖
            else 
                t[x].pos = t[x].l; // 未被覆盖
        } else {
            pushup(x);  // 非叶子节点，向上更新
        }
        return;
    }
    
    // 递归处理左右子区间
    if (y <= t[x << 1].r)
        add(x << 1, y, min(z, t[x << 1].r), w);
    if (z > t[x << 1].r)
        add((x << 1) | 1, max(y, t[x << 1].r + 1), z, w);
    
    pushup(x);
}

2. 向上更新 pushup(x)

void pushup(int x) {
    if (t[x].flg)
        t[x].pos = 0;  // 整个区间被覆盖
    else if (t[x << 1].pos)
        t[x].pos = t[x << 1].pos;  // 左子树有未覆盖位置
    else
        t[x].pos = t[(x << 1) | 1].pos;  // 否则取右子树
}

---

算法流程详解

数据结构

int p[3][N];  // p[j][i] = 场地j上排名第i的选手编号
int q[3][N];  // q[j][x] = 选手x在场地j上的排名（p的反向索引）

初始化

// 读入排名并建立反向索引
for (int j = 0; j < 3; ++j) {
    for (int i = 1; i <= n; ++i) {
        cin >> p[j][i];
        q[j][p[j][i]] = i;  // 选手p[j][i]在场地j的排名是i
    }
}

// 建立线段树
seg.build(1, 1, n);

// 为每个选手添加覆盖
for (int i = 1; i <= n; ++i)
    add(i, 1);

添加/删除选手覆盖

void add(int x, int y) {
    // 如果选手x在三个场地排名相同，跨度为0，不需要覆盖
    if (q[0][x] == q[1][x] && q[1][x] == q[2][x])
        return;
    
    int mini = min(q[0][x], min(q[1][x], q[2][x]));  // 最好排名
    int maxi = max(q[0][x], max(q[1][x], q[2][x]));  // 最差排名
    
    // 在区间[mini, maxi-1]上添加y次覆盖
    seg.add(1, mini, maxi - 1, y);
}

数学解释：

• 选手 $x$ 覆盖区间 $[\text{best}[x], \text{worst}[x] - 1]$
• $y = 1$ 表示添加覆盖，$y = -1$ 表示移除覆盖

查询操作

if (x == 1) {
    int ps = seg.t[1].pos;  // 获取临界点
    
    if (max(q[0][y], max(q[1][y], q[2][y])) <= ps) {
        cout << "DA\n";  // worst[y] <= pos，能夺冠
    } else {
        cout << "NE\n";  // worst[y] > pos，不能夺冠
    }
}

判定逻辑：

$$\text{选手 } y \text{ 能夺冠} \Leftrightarrow \max(q[0][y], q[1][y], q[2][y]) \leq \text{seg.t[1].pos} $$

修改操作

else {  // x == 2
    cin >> z >> w;
    
    // 移除z和w的旧覆盖
    add(z, -1);
    add(w, -1);
    
    // 交换排名
    swap(q[y - 1][z], q[y - 1][w]);
    
    // 添加z和w的新覆盖
    add(z, 1);
    add(w, 1);
}

步骤解释：

1. 先删除选手 $z$ 和 $w$ 的旧覆盖区间
2. 交换他们在场地 $y-1$ 上的排名
3. 重新计算并添加新的覆盖区间

---

复杂度分析

时间复杂度

• 初始化： $O(N \log N)$ - 为每个选手添加覆盖
• 查询操作： $O(\log N)$ - 查询线段树根节点
• 修改操作： $O(\log N)$ - 4次线段树区间修改
• 总复杂度： $O((N + Q) \log N)$

相比朴素算法的 $O(QN)$，在 $Q$ 较大时有显著优化。

空间复杂度

$O(N)$ - 线段树和排名数组

---

正确性证明总结

核心不变式

线段树维护的不变式： seg.t[1].pos 始终等于最小的未被任何选手覆盖的排名位置。

算法正确性

1. 初始状态： 所有选手的覆盖区间都已添加到线段树
2. 查询正确性： 基于引理，$\text{worst}[y] \leq \text{pos}$ 等价于 $y$ 能夺冠
3. 修改正确性： 交换排名后，重新计算覆盖区间，保持不变式

---

算法亮点

1. 数学抽象： 将"支配关系"转化为"排名跨度"和"覆盖区间"
2. 临界点思想： 用一个全局临界点 $\text{pos}$ 统一判定所有选手
3. 高效维护： 线段树实现 $O(\log N)$ 的动态维护和查询
4. 优雅简洁： 判定条件从 $O(N)$ 遍历简化为一次大小比较