The problem determines which players can win a tournament across three courts with distinct rankings. A player defeats another if they have a better (lower) rank in any court.

Key Insight

Each player is represented by their worst (maximum) rank across all courts, denoted as $m_i$. The set of potential winners forms a contiguous prefix of players sorted by $m_i$. The thresohld $k$ is the smallest integer where exactly $k$ players have $m_i \leq k$. Players below this threshold can win.

Data Structure

Maintain an aray where each entry corresponds to a threshold candidate. For each player, increment the range $[m_i, n]$. The threshold $k$ is the first position where the cumulative value (initialized as $-i$) becomes zero. Use a segment tree supporting:

• Range addition
• Binary search for the first zero value

Operations

1. Initialization: Compute $m_i$ for each player and apply range adidtions to the segment tree.
2. Win Check (Type 1): Verify if $m_x \leq k$ for player $x$.
3. Swap Players (Type 2): Update rankings in a court, adjust affected $m_i$ values, and recompute contributions in the segment tree.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct SegTree {
    struct Node {
        int mx, lz, l, r;
    };
    vector<Node> t;
    int n;

    SegTree(int sz) : n(sz) {
        t.resize(4*sz);
        build(1, 1, n);
    }

    void build(int i, int l, int r) {
        t[i] = { -l, 0, l, r };
        if (l == r) return;
        int m = (l+r)/2;
        build(2*i, l, m);
        build(2*i+1, m+1, r);
        t[i].mx = max(t[2*i].mx, t[2*i+1].mx);
    }

    void push(int i) {
        if (t[i].lz) {
            for (int c : {2*i, 2*i+1}) {
                t[c].mx += t[i].lz;
                t[c].lz += t[i].lz;
            }
            t[i].lz = 0;
        }
    }

    void upd(int i, int l, int r, int v) {
        if (l > t[i].r || r < t[i].l) return;
        if (l <= t[i].l && t[i].r <= r) {
            t[i].mx += v;
            t[i].lz += v;
            return;
        }
        push(i);
        upd(2*i, l, r, v);
        upd(2*i+1, l, r, v);
        t[i].mx = max(t[2*i].mx, t[2*i+1].mx);
    }

    int findZero(int i) {
        if (t[i].l == t[i].r) return t[i].l;
        push(i);
        if (t[2*i].mx == 0) return findZero(2*i);
        return findZero(2*i+1);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<vector<int>> court(3, vector<int>(n+1));
    for (int c = 0; c < 3; c++)
        for (int i = 1; i <= n; i++)
            cin >> court[c][i];

    vector<vector<int>> pos(3, vector<int>(n+1));
    for (int c = 0; c < 3; c++)
        for (int i = 1; i <= n; i++)
            pos[c][court[c][i]] = i;

    vector<int> maxRank(n+1);
    for (int i = 1; i <= n; i++)
        maxRank[i] = max({pos[0][i], pos[1][i], pos[2][i]});

    SegTree st(n);
    for (int i = 1; i <= n; i++)
        st.upd(1, maxRank[i], n, 1);

    int sep = st.findZero(1);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int p;
            cin >> p;
            cout << (maxRank[p] <= sep ? "DA\n" : "NE\n");
        } else {
            int c, a, b;
            cin >> c >> a >> b;
            c--;
            st.upd(1, maxRank[a], n, -1);
            st.upd(1, maxRank[b], n, -1);
            swap(pos[c][a], pos[c][b]);
            maxRank[a] = max({pos[0][a], pos[1][a], pos[2][a]});
            maxRank[b] = max({pos[0][b], pos[1][b], pos[2][b]});
            st.upd(1, maxRank[a], n, 1);
            st.upd(1, maxRank[b], n, 1);
            sep = st.findZero(1);
        }
    }
    return 0;
}