题目大意

有 $n$ 名选手参加三项比赛，每项比赛给出完整的排名（无并列）。定义「道德上优于」关系：

1. 如果在至少两项比赛中 $a$ 的排名优于 $b$，则 $a$ 道德上优于 $b$
2. 该关系具有传递性：如果 $a$ 优于 $c$ 且 $c$ 优于 $b$，则 $a$ 优于 $b$

回答 $m$ 个查询：选手 $a$ 是否在道德上优于选手 $b$？

问题分析

这是一个典型的有向图传递闭包问题。

关键观察

1. 直接比较关系：对于任意两个选手 $i$ 和 $j$，统计在多少项比赛中 $i$ 排名优于 $j$
2. 图论建模：如果 $i$ 在至少两项比赛中优于 $j$，则存在有向边 $i \to j$
3. 传递闭包：由于关系具有传递性，需要计算图的传递闭包

算法思路

方法1：Floyd-Warshall 算法（适用于小数据）

对于 $n \leq 300$，可以直接使用 Floyd-Warshall 算法计算传递闭包。

步骤：

1. 构建邻接矩阵 $adj$，其中 $adj[i][j] = 1$ 当且仅当 $i$ 在至少两项比赛中优于 $j$
2. 使用 Floyd-Warshall 算法计算传递闭包
3. 对于每个查询，直接查表回答

时间复杂度： $O(n^3)$

方法2：强连通分量缩点 + DAG 传递闭包（适用于大数据）

对于 $n \leq 500000$，需要更高效的算法。

步骤：

1. 构建图：根据直接比较关系建立有向图
2. 求强连通分量：使用 Kosaraju 或 Tarjan 算法
3. 缩点：将每个强连通分量缩成一个点，得到 DAG
4. 拓扑排序：对 DAG 进行拓扑排序
5. 计算传递闭包：使用位集优化或动态规划

代码实现

方法1实现（$n \leq 300$）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<int>> rank(3, vector<int>(n + 1));
    vector<vector<int>> pos(3, vector<int>(n + 1));
    
    // 读取排名数据
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            rank[i][j] = x;
            pos[i][x] = j;  // 记录每个选手在该比赛中的名次
        }
    }
    
    // 构建直接比较关系图
    vector<vector<bool>> direct(n + 1, vector<bool>(n + 1, false));
    vector<vector<bool>> reach(n + 1, vector<bool>(n + 1, false));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            
            int cnt = 0;
            for (int k = 0; k < 3; k++) {
                if (pos[k][i] < pos[k][j]) {  // i 的排名比 j 好（名次数值小）
                    cnt++;
                }
            }
            if (cnt >= 2) {
                direct[i][j] = true;
                reach[i][j] = true;
            }
        }
    }
    
    // Floyd-Warshall 计算传递闭包
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (reach[i][k] && reach[k][j]) {
                    reach[i][j] = true;
                }
            }
        }
    }
    
    int m;
    cin >> m;
    
    while (m--) {
        int a, b;
        cin >> a >> b;
        
        if (reach[a][b]) {
            cout << "TAK\n";
        } else {
            cout << "NIE\n";
        }
    }
    
    return 0;
}

方法2思路（$n \leq 500000$）

对于大数据，需要使用更高效的算法：

#include <bits/stdc++.h>
using namespace std;

class SCC {
private:
    int n;
    vector<vector<int>> adj;
    vector<int> disc, low, comp;
    vector<bool> inStack;
    stack<int> st;
    int time, sccCount;
    
    void dfs(int u) {
        disc[u] = low[u] = ++time;
        st.push(u);
        inStack[u] = true;
        
        for (int v : adj[u]) {
            if (disc[v] == -1) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = min(low[u], disc[v]);
            }
        }
        
        if (low[u] == disc[u]) {
            while (true) {
                int v = st.top(); st.pop();
                inStack[v] = false;
                comp[v] = sccCount;
                if (v == u) break;
            }
            sccCount++;
        }
    }
    
public:
    SCC(int n, const vector<vector<int>>& graph) : n(n), adj(graph) {
        disc.assign(n + 1, -1);
        low.assign(n + 1, -1);
        comp.assign(n + 1, -1);
        inStack.assign(n + 1, false);
        time = sccCount = 0;
        
        for (int i = 1; i <= n; i++) {
            if (disc[i] == -1) {
                dfs(i);
            }
        }
    }
    
    int getComp(int u) { return comp[u]; }
    int getCount() { return sccCount; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<int>> rank(3, vector<int>(n + 1));
    vector<vector<int>> pos(3, vector<int>(n + 1));
    
    for (int i = 0; i < 3; i++) {
        for (int j = 1; j <= n; j++) {
            int x;
            cin >> x;
            rank[i][j] = x;
            pos[i][x] = j;
        }
    }
    
    // 构建图
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            
            int cnt = 0;
            for (int k = 0; k < 3; k++) {
                if (pos[k][i] < pos[k][j]) {
                    cnt++;
                }
            }
            if (cnt >= 2) {
                graph[i].push_back(j);
            }
        }
    }
    
    // 计算强连通分量
    SCC scc(n, graph);
    int compCount = scc.getCount();
    
    // 构建缩点后的DAG
    vector<set<int>> dag(compCount);
    vector<int> compSize(compCount, 0);
    
    for (int i = 1; i <= n; i++) {
        compSize[scc.getComp(i)]++;
    }
    
    for (int u = 1; u <= n; u++) {
        for (int v : graph[u]) {
            int compU = scc.getComp(u);
            int compV = scc.getComp(v);
            if (compU != compV) {
                dag[compU].insert(compV);
            }
        }
    }
    
    // 拓扑排序
    vector<int> indegree(compCount, 0);
    for (int i = 0; i < compCount; i++) {
        for (int j : dag[i]) {
            indegree[j]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < compCount; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> topoOrder;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topoOrder.push_back(u);
        
        for (int v : dag[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 计算DAG的传递闭包（使用位集优化）
    vector<bitset<500000>> reach(compCount);
    for (int i = compCount - 1; i >= 0; i--) {
        int u = topoOrder[i];
        reach[u][u] = 1;
        for (int v : dag[u]) {
            reach[u] |= reach[v];
        }
    }
    
    int m;
    cin >> m;
    
    while (m--) {
        int a, b;
        cin >> a >> b;
        
        int compA = scc.getComp(a);
        int compB = scc.getComp(b);
        
        if (compA == compB || reach[compA][compB]) {
            cout << "TAK\n";
        } else {
            cout << "NIE\n";
        }
    }
    
    return 0;
}

复杂度分析

方法1：

• 构建图：$O(n^2)$
• Floyd-Warshall：$O(n^3)$
• 查询：$O(1)$ 每个查询
• 总复杂度：$O(n^3 + m)$，适用于 $n \leq 300$

方法2：

• 构建图：$O(n^2)$
• 强连通分量：$O(n + E)$，其中 $E \leq n^2$
• 拓扑排序：$O(n + E)$
• 传递闭包：$O(n^2/w)$，其中 $w$ 是字长（位集优化）
• 总复杂度：$O(n^2 + m)$，适用于大数据

优化技巧

1. 位集优化：使用 bitset 来存储传递闭包，将复杂度除以字长
2. 输入优化：使用快速输入输出
3. 内存优化：对于稀疏图，使用邻接表而非邻接矩阵

总结

本题的核心是将比较关系转化为图论问题，通过计算有向图的传递闭包来回答查询。根据数据规模选择合适的算法：

• 小数据：直接 Floyd-Warshall
• 大数据：强连通分量缩点 + DAG 传递闭包 + 位集优化