This article presents the solution for the first daily problem from HydroOJ (September 3, 2021): [COCI2018-2019 Final T4] TENIS.

Problem Statement

Vito is organizing a tennis tournament with n players (numbered 1 to n). He has ranking lists for three court types: clay, grass, and hard court. The tournament consists of n−1 matches. In each match, two remaining players compete on a chosen court; the lower‑ranked player on that court is eliminated. The last remaining player wins.

Vito can control the outcome by selecting which players face each other and on which court, but only among those still in the tournament. He occasionally updates the rankings (swapping two players' positions on one court) and receives queries: "Can player x become champion?". Write a program that handles updates and answers queries.

Solution Overview

This is a graph‑theoretic problem with a clever data structure.

Key observation

Consider player i. On any court where i is stronger than j, i can defeat j. If we build a directed graph where an edge from i to j exists if i beats j on at least one court, then i can become champion iff i can reach all other nodes. But naively checking this for each query is O(n) → O(nQ) too slow.

Compressed representation

Instead of explicit edges, note that each player i has three ranks: r1, r2, r3. The strongest rank among these three determines the "reach" of i: any player with a strictly smaller rank on some court is beatable. Therefore, if we sort players by their worst rank (the maximum of the three), interesting structure emerges.

Main idea: The split line

Sort players by their best (minimum) rank. There exists a threshold k such that all players with best rank ≤ k can defeat each other (and hence the whole set), while players with best rank > k cannot defeat all those below k. This threshold is called the split line and can be maintained dynamically.

Data structure

Define a array A[1…n]. Initially A[r] = –r. For each player i, let R = max(rank on court1, court2, court3). We add +1 to all positions from R to n. After processing all players, the smallest index ℓ where A[ℓ] = ℓ is the split line. Why? Because the number of players whose highest rank is ≤ ℓ is exactly ℓ.

Supported operations

• Range add (when updating two players’ positions)
• Find the leftmost index with A[index] = index

We use a segment tree storing the maximum value in each node, with lazy propagation. The leaf at position i stores –i. After all updates, we query the tree: if the left child’s maximum is 0 (or negative exactly zero after corrections), answer is in the left child; else in the right child.

Complexity

O((n + Q) log n)

Implementation

Below is the rewritten C++ code with modified variable names and logic structure.

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

const int MAXN = 100005;

int n, q, rank[4][MAXN], threshold;

struct SegTree {
    int l, r, mx, lazy;
} tree[MAXN << 2];

#define lc (x << 1)
#define rc (x << 1 | 1)

void build(int x, int l, int r) {
    tree[x].l = l; tree[x].r = r;
    if (l == r) {
        tree[x].mx = -l;
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    tree[x].mx = max(tree[lc].mx, tree[rc].mx);
}

void push(int x) {
    if (tree[x].lazy == 0) return;
    tree[lc].lazy += tree[x].lazy;
    tree[rc].lazy += tree[x].lazy;
    tree[lc].mx += tree[x].lazy;
    tree[rc].mx += tree[x].lazy;
    tree[x].lazy = 0;
}

void add(int x, int l, int r, int val) {
    if (l <= tree[x].l && tree[x].r <= r) {
        tree[x].lazy += val;
        tree[x].mx += val;
        return;
    }
    push(x);
    int mid = (tree[x].l + tree[x].r) >> 1;
    if (l <= mid) add(lc, l, r, val);
    if (r > mid) add(rc, l, r, val);
    tree[x].mx = max(tree[lc].mx, tree[rc].mx);
}

int query(int x, int l, int r) {
    if (l == r) return l;
    push(x);
    int mid = (l + r) >> 1;
    if (tree[lc].mx == 0) return query(lc, l, mid);
    return query(rc, mid + 1, r);
}

void updatePlayer(int id, int delta) {
    int worst = max({rank[1][id], rank[2][id], rank[3][id]});
    add(1, worst, n, delta);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    build(1, 1, n);

    for (int court = 1; court <= 3; ++court) {
        for (int pos = 1; pos <= n; ++pos) {
            int player;
            cin >> player;
            rank[court][player] = pos;
        }
    }

    for (int i = 1; i <= n; ++i) updatePlayer(i, 1);
    threshold = query(1, 1, n);

    int op, x, y, z;
    while (q--) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            cout << (rank[1][x] <= threshold ? "DA" : "NE") << '\n';
        } else {
            cin >> z >> x >> y;
            updatePlayer(x, -1);
            updatePlayer(y, -1);
            swap(rank[z][x], rank[z][y]);
            updatePlayer(x, 1);
            updatePlayer(y, 1);
            threshold = query(1, 1, n);
        }
    }
    return 0;
}