2025 广工新生赛（初赛）题解

先换个说法。设第 t 次匹配用的是 T 的后缀 T[q_t..|T|]（长度 L_t = |T|-q_t+1），它出现在 S 的 i_t 处。那么必须 q_t 严格递增，且 i_{t+1} ≥ i_t + L_t（不重叠、从左到右）。删除操作只负责把 q 从 q_t 推到 q_{t+1}，随时可做，所以一条这样的链一定对应一个合法操作序列，反之亦然。问题就是求最长链。

关键标准化：任何一条长 k 的链，都可以换成「长度恰为 k, k-1, ..., 1」的链。理由：T 的长 L 后缀以 T 的长 L' 后缀（L' 小于 L）为后缀，所以若长 L 后缀出现在 i，则长 L' 后缀出现在 i + (L - L')；令 j_t = i_t + (L_t - (k-t+1))，逐项验证 j_{t+1} ≥ j_t + (k-t+1)，不等号两边只差 (i_{t+1} - i_t - L_t) + L_{t+1} - (k-t) ≥ 0，成立。于是「能取 k 次」等价于「把长度 k, k-1, ..., 1 的后缀依次塞进 S」。

长度序列固定后，贪心就是最优：每个后缀取它能取到的最左出现位置。长度固定时起点最左等价于终点最左，留给后面的 S 最多，这是标准交换论证。所以判定 k 只需要从左往右扫一遍，复杂度 O(|S|)。

判定对 k 单调：长度为 k 的标准链去掉第一段就是 k-1 的标准链，所以二分答案。又因为 1+2+...+k ≤ |S|，k 上界是 632（|S| = 2×10^5），二分只要 10 次判定。

「T 的长 L 后缀在 S 中最左出现在哪」用一次 Z 函数解决：把 S、T 都反转，T 的后缀变成 T' 的前缀，在 T'+'#'+S' 上跑 Z，z 值就是 S' 某位置与 T' 的 LCP，于是 O(1) 判定某个位置能否放长度 L 的后缀。总复杂度 O(|S| + |T| + |S| log min(|T|, 632))。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S, T;
    if (!(cin >> S >> T)) return 0;
    int n = S.size(), m = T.size();

    // 反转后 T 的后缀变成 T' 的前缀：一次 Z 函数就能 O(1) 判断任意位置能否放任意长度的后缀
    string Sr(S.rbegin(), S.rend()), Tr(T.rbegin(), T.rend());
    string U = Tr + "#" + Sr;
    int len = U.size();
    vector<int> z(len, 0);
    for (int i = 1, l = 0, r = 0; i < len; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < len && U[z[i]] == U[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    int base = m + 1;                        // U 中 S' 部分的起点
    auto ok = [&](int i, int L) {            // S[i..i+L-1] 是否等于 T 的长 L 后缀
        return z[base + (n - i - L)] >= L;   // 对应到 S' 里的起点是 n-i-L
    };
    auto check = [&](int k) {                // 长度 k,k-1,...,1 的标准链能否塞进 S
        int p = 0;
        for (int L = k; L >= 1; L--) {
            int i = p;                       // 每个后缀都取能取到的最左位置
            while (i + L <= n && !ok(i, L)) i++;
            if (i + L > n) return false;
            p = i + L;                       // 下一段必须从这里之后开始
        }
        return true;
    };

    int hi = min(m, (int)((sqrt(8.0 * n + 1) - 1) / 2));  // 1+2+...+k 不能超过 |S|
    int lo = 0;
    while (lo < hi) {                        // 可行性对 k 单调，二分
        int mid = (lo + hi + 1) >> 1;
        if (check(mid)) lo = mid; else hi = mid - 1;
    }
    cout << lo << '\n';
    return 0;
}

老虎只在它所在的行里活动，所以小猪走到 (x, y) 时只可能撞上第 x 行的老虎。这一条把「与所有老虎判重」降成「与一只老虎判重」。

单只老虎在一行内左右折返，位置是周期 2(m-1) 的三角波。取相位：初始方向 R 时相位 = c-1，初始方向 L 时相位 = 2(m-1)-(c-1)；那么做完 t 次移动后，位置列号是令 x = (相位+t) mod 2(m-1)，若 x ≤ m-1 则是 1+x，否则是 2m-1-x。这样任意时刻位置 O(1) 求出。注意 m = 2 时周期是 2，公式依然成立。

所有老虎的周期都是 2(m-1)（与初始位置无关），所以整个局面以 2(m-1) 为周期重复。于是 BFS 的状态是 (行, 列, t mod 2(m-1))，状态数 n·m·2(m-1) ≤ 100·100·198 ≈ 2×10^6，每个状态枚举 5 种移动。

转移要按题目时序检查两次：小猪先动，落点不能是时刻 t 的老虎格；然后老虎动，落点不能是时刻 t+1 的老虎格。两次都过了才把 (nr, nc, (t+1) mod 周期) 入队；若落点就是 (n,1) 且第二次检查通过，直接输出 YES。

为什么状态里一定要带时间？同一个格子在时刻 t 和 t + 2(m-1) 是同一局面，但在时刻 t 与 t+1 的生死判断完全不同；只用 (行,列) 做 BFS 会漏掉「必须等老虎走开」的解，也会把不同时刻混成一点。

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

int main() {
    int n, m;
    if (scanf("%d %d", &n, &m) != 2) return 0;
    vector<int> c(n);
    vector<char> d(n);
    for (int i = 0; i < n; i++) scanf("%d %c", &c[i], &d[i]);

    int P = 2 * (m - 1);                     // 老虎位置的周期
    vector<int> ph(n);
    for (int i = 0; i < n; i++) {
        int x = c[i] - 1;
        ph[i] = (d[i] == 'R') ? x : (P - x) % P;   // 相位：位置只由 (ph + t) % P 决定
    }
    auto pos = [&](int row, int t) {          // 第 row 行老虎在时刻 t 的列号（1-indexed）
        int x = (ph[row] + t) % P;
        return x <= m - 1 ? 1 + x : 2 * m - 1 - x;   // 超过 m 的部分折返
    };

    vector<char> vis((size_t)n * m * P, 0);
    auto id = [&](int r, int col, int t) { return ((size_t)r * m + col) * P + t; };
    vector<int> q;
    int st = (int)id(0, m - 1, 0);            // 起点 (1, m)，0-indexed 是 (0, m-1)
    q.push_back(st);
    vis[st] = 1;
    const int dr[5] = {-1, 1, 0, 0, 0}, dc[5] = {0, 0, -1, 1, 0};
    for (size_t h = 0; h < q.size(); h++) {
        int cur = q[h];
        int t = cur % P, cell = cur / P, r = cell / m, col = cell % m;
        for (int k = 0; k < 5; k++) {
            int nr = r + dr[k], nc = col + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (nc + 1 == pos(nr, t)) continue;      // 小猪先动：落点上正站着老虎
            int t2 = (t + 1) % P;
            if (nc + 1 == pos(nr, t2)) continue;     // 老虎后动：不能被踩到
            if (nr == n - 1 && nc == 0) { puts("YES"); return 0; }
            int nid = (int)id(nr, nc, t2);
            if (!vis[nid]) { vis[nid] = 1; q.push_back(nid); }
        }
    }
    puts("NO");
    return 0;
}

要灭掉玄真国，就得让每个 i 挨 a_i 刀，共 SA = Σa_i 场有效战斗；每场战斗同时消耗一个 b_j，所以第 j 个宗派最多被消耗 b_j 次。也就是说：把 a_i 份「需求」分给各个 j（i ≠ j），每个 j 收不超过 b_j 份。这就是一个运输问题（源 i 供应 a_i，汇 j 容量 b_j，只缺 i = j 的边），存在解等价于存在这样的分配。

有了分配表就能排出战斗顺序：任一时刻某宗派剩余人数 = 初始值减去已消耗，而总消耗不超过初值，所以随便什么顺序都不会出现「没人可派」。因此分配存在 ⟺ 战斗序列存在。

按霍尔条件（最大流最小割）判可行性：对任意源集合 X，Σ_{i∈X} a_i 不能超过 X 能连到的汇容量和。若 |X| ≥ 2，任取 i∈X 与任一 j，只要 j ≠ i 就有边，所以 X 连到全部汇，条件是 SA ≤ SB。若 X = {i}，连到的汇是除 i 外的全部，条件是 a_i ≤ SB - b_i，即 a_i + b_i ≤ SB。

于是：能灭甲方 ⟺ SA ≤ SB 且 max(a_i + b_i) ≤ SB；能灭乙方 ⟺ SB ≤ SA 且 max(a_i + b_i) ≤ SA。两个都不成立就输出 NO。注意 n = 1 时 a_1 + b_1 必然大于 SB 与 SA，自动判 NO，和样例一致。

输出第一场：注意「SA ≤ SB」在双方各减 1 后仍然成立（同时减 1 不改变大小关系），所以计划不会因为这一刀而改变。设当前计划上限为 lim（灭甲取 SB、灭乙取 SA），开战后要求 max(a_k+b_k) ≤ lim 变成 ≤ lim-1；只有 i、j 两行会减 1，因此所有满足 a_k + b_k = lim 的下标 k 必须都落在 {i, j} 里。这样的下标至多 2 个：0 个则任取 i ≠ j，1 个则让它当 i，2 个则直接取 {i, j}。

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

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        int n; scanf("%d", &n);
        vector<ll> a(n), b(n);
        ll SA = 0, SB = 0, M = 0;
        for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); SA += a[i]; }
        for (int i = 0; i < n; i++) { scanf("%lld", &b[i]); SB += b[i]; }
        for (int i = 0; i < n; i++) M = max(M, a[i] + b[i]);

        // 灭甲方：SA <= SB 且 max(a_i+b_i) <= SB；灭乙方对称
        bool okA = (SA <= SB) && (M <= SB);
        bool okB = (SB <= SA) && (M <= SA);

        // 在上限 lim 下挑第一场：所有 a_k+b_k == lim 的 k 都必须被 {i,j} 覆盖
        auto pick = [&](ll lim, int &ii, int &jj) -> bool {
            if (n < 2) return false;
            vector<int> z;
            for (int k = 0; k < n; k++) if (a[k] + b[k] == lim) z.push_back(k);
            if (z.size() > 2) return false;              // 一刀只能照顾两行
            if (z.size() == 2) { ii = z[0]; jj = z[1]; return true; }
            if (z.size() == 1) { ii = z[0]; jj = (z[0] == 0 ? 1 : 0); return true; }
            ii = 0; jj = 1; return true;                 // 没人卡在上限，随便打
        };

        int ii = -1, jj = -1;
        bool got = false;
        if (okA) got = pick(SB, ii, jj);
        if (!got && okB) got = pick(SA, ii, jj);         // SA == SB 时两种计划的覆盖条件相同
        if (!got) { puts("NO"); continue; }
        puts("YES");
        printf("%d %d\n", ii + 1, jj + 1);               // 输出 1-indexed
    }
    return 0;
}

只看每个数 mod 3。设区间内余 0、1、2 的个数分别是 c0、c1、c2。

c0 ≥ 1 时直接取那个数，和为 3 的倍数，成立。否则只能用余 1 和余 2 的数凑。1+1+1 = 3，2+2+2 = 6，1+2 = 3，这三种组合都成立；反过来，任何和 ≡ 0 (mod 3) 的非空组合，把 1 和 2 尽量配成对之后，剩下的全是同一种余数，必须凑够三个才能再次被 3 整除。所以判定就是三种组合之一可行。

所以答案 = (c0 ≥ 1) 或 (c1 ≥ 1 且 c2 ≥ 1) 或 (c1 ≥ 3) 或 (c2 ≥ 3)。

对三类余数各做一遍前缀和，每个询问 O(1)。预处理 O(n)、总复杂度 O(n + q)，与 a_i 的大小无关（也不需要真的求和，避免 10^9 × 10^5 溢出）。

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

int main() {
    int n, q;
    if (scanf("%d %d", &n, &q) != 2) return 0;
    vector<array<int, 3>> pre(n + 1);      // pre[i][r] = 前 i 个数里余 r 的个数
    pre[0] = {0, 0, 0};
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        pre[i] = pre[i - 1];
        pre[i][x % 3]++;
    }
    while (q--) {
        int l, r; scanf("%d %d", &l, &r);
        int c0 = pre[r][0] - pre[l - 1][0];
        int c1 = pre[r][1] - pre[l - 1][1];
        int c2 = pre[r][2] - pre[l - 1][2];
        bool ok = c0 >= 1 || (c1 >= 1 && c2 >= 1) || c1 >= 3 || c2 >= 3;
        puts(ok ? "Yes" : "No");
    }
    return 0;
}

思路一（交互派）：逐位确定。先输出 m = 0，得到 c = popcount(p)。之后每次输出 m = 2^i，若 p 的第 i 位是 0，则 d 比 p 多一个 1，回复 c+1；若是 1，则回复 c-1。一次查询换来一个 bit，候选集合每次都缩小一半。p 有 60 个 bit：1 次求 c、59 次定下第 0..58 位，第 59 位由 c 减去已知的 1 的个数直接算出，最后输出 p 收 0，共 1+59+1 = 61 次，小于 64。

思路二（分解派，也是代码走的路）：n ≤ 2^60，直接做质因数分解就能拿到最大质因子，第一次尝试输出 m = p 就立刻收到 0，只用 1 次机会。题目叫「模板」就是在提示这条路，提示说明里也写了「只需要写一个高效率的质因数分解算法」。

分解的两个部件：Miller-Rabin 判素（用前 12 个质数当底，对 2^60 以内的数完全确定，不会误判），以及 Pollard-Rho 找因子（随机 c 与起点，用 Floyd 判圈在 O(n^{1/4}) 期望步数内找到非平凡因子）。n 不超过 2^60 时最坏是「两个 30 位质数相乘」，需要约 3×10^4 次迭代，而每次迭代是几次 128 位取模乘法，非常快。

递归分解：n 是质数就更新答案；否则找到一个因子 d，递归处理 d 与 n/d。注意每层都要判素，因为 Pollard-Rho 只能保证返回一个非平凡因子（可能还是合数）。

交互侧只需三步：读 n、分解、输出 p 并 fflush，然后读掉那行 0 再退出。千万不要在收到 0 之后继续输出，会被判协议错误。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __int128 lll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ull mulmod(ull a, ull b, ull m) { return (ull)((lll)a * b % m); }   // 防溢出

ull powmod(ull a, ull e, ull m) {
    ull r = 1 % m;
    a %= m;
    while (e) {
        if (e & 1) r = mulmod(r, a, m);
        a = mulmod(a, a, m);
        e >>= 1;
    }
    return r;
}

// 前 12 个质数作底，对 n < 3.3e24 都是确定的，2^60 内绝不会误判
bool isPrime(ull n) {
    if (n < 2) return false;
    for (ull p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL})
        if (n % p == 0) return n == p;
    ull d = n - 1;
    int s = 0;
    while (!(d & 1)) { d >>= 1; s++; }
    for (ull a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        ull x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { comp = false; break; }
        }
        if (comp) return false;
    }
    return true;
}

// Floyd 判圈版 Pollard-Rho：找到 n 的一个非平凡因子（n 为合数时）
ull pollard(ull n) {
    if (n % 2 == 0) return 2;
    while (true) {
        ull c = rng() % (n - 1) + 1;
        ull x = rng() % (n - 2) + 2, y = x, d = 1;
        auto f = [&](ull v) { return (mulmod(v, v, n) + c) % n; };
        while (d == 1) {
            x = f(x);                       // 一步一步
            y = f(f(y));                    // 两步，相遇即出环
            d = __gcd(x > y ? x - y : y - x, n);
        }
        if (d != n) return d;               // d == n 说明这一轮退化，换 c 重来
    }
}

ull best = 1;                               // 最大质因子

void factor(ull n) {
    if (n < 2) return;
    if (isPrime(n)) { best = max(best, n); return; }
    ull d = pollard(n);
    factor(d);
    factor(n / d);
}

int main() {
    ull n;
    if (scanf("%llu", &n) != 1) return 0;
    factor(n);
    printf("%llu\n", best);                 // 第一次尝试就报出 p
    fflush(stdout);                         // 交互题必须刷新
    int c = 0;
    if (scanf("%d", &c) == 1) { /* 这里收到 0，代表猜对了 */ }
    return 0;
}

n+1 ≡ 0 (mod n+1)，所以它的前缀和不会改变当前余数。若把它插在 p_1..p_k 之后（k ≥ 1），则 S_{k+1} = S_k，两个值相等，立即不合法。

因此插入位置只能是开头：q = (n+1, p_1, p_2, ..., p_n)。此时 S_1 = n+1 ≡ 0，而 k ≥ 2 时 S_k 就是 p 的前 k-1 个前缀和 mod (n+1)。

于是条件变成：p 的 n 个前缀和 mod (n+1) 两两不同，而且都不能等于 0（0 已经被 S_1 占了）。n+1 个余数正好 0..n，所以这 n 个值必须恰好是 1..n。

扫一遍 p、用桶判重（同时把 0 预标记为已用）即可，O(n)。注意多组测试要按 n+1 的大小开桶，不要每组都 memset 一个 10^6 的数组。

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

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        int n; scanf("%d", &n);
        vector<int> p(n + 1);
        for (int i = 1; i <= n; i++) scanf("%d", &p[i]);

        int m = n + 1;                       // n+1 ≡ 0，插在中间会让相邻两个前缀和相等
        vector<char> seen(m, 0);
        seen[0] = 1;                         // S_1 = 0 已经占用了余数 0
        long long s = 0;
        bool ok = true;
        for (int i = 1; i <= n; i++) {
            s = (s + p[i]) % m;
            if (seen[s]) { ok = false; break; }
            seen[s] = 1;
        }
        if (!ok) { puts("-1"); continue; }
        printf("%d", m);
        for (int i = 1; i <= n; i++) printf(" %d", p[i]);
        puts("");
    }
    return 0;
}

由上一题：只有把 n+1 放在开头才可能合法，等价条件是 p 的 n 个前缀和 mod m（m = n+1）两两不同且都不为 0。n 个互不相同的非零余数正好占满 1..m-1，于是最后一个前缀和 = 1+2+...+n = n(n+1)/2 必须不等于 0 mod m。

若 m 是奇数，(m-1)/2 是整数，n(n+1)/2 = m(m-1)/2 ≡ 0 (mod m)，矛盾。所以 m 必须偶数，即 n 必须奇数；n 为偶数时直接输出 -1。这也解释了样例里 n = 2 输出 -1。

n 为奇数（m 偶数）时给出构造。取 p = (m-1, 2, m-3, 4, m-5, 6, ..., 1)，也就是奇数位依次放 m-1, m-3, ..., 1，偶数位依次放 2, 4, ..., m-2。

验证：设 p 的第 2i 项是 2i，第 2i-1 项是 m-(2i-1)。则第 2i 个前缀和 = i·m + i ≡ i，第 2i-1 个前缀和 = i·m - i ≡ m-i。于是前缀和集合是 {1,...,m/2-1} ∪ {m/2,...,m-1} = 1..m-1，全部非零、全部互异，正好满足要求。

复杂度 O(n)（每个数只输出一次），比「搜索构造」靠谱得多；而且这组 p 直接可以作为上一题的输入，两题互相对拍很合适。

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

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        int n; scanf("%d", &n);
        if (n % 2 == 0) { puts("-1"); continue; }   // m 为奇数时总和必为 0 mod m，无解
        int m = n + 1;                              // 偶数
        // p = (m-1, 2, m-3, 4, ..., 1)：差分出的前缀和覆盖 1..m-1
        vector<int> p(n);
        int odd = m - 1, even = 2;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) { p[i] = odd; odd -= 2; }
            else { p[i] = even; even += 2; }
        }
        for (int i = 0; i < n; i++) printf("%d%c", p[i], i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

全部下标对是 C(n,2) = n(n-1)/2 个，需要去掉 a_i = a_j 的。

对每个值 v，若出现 cnt[v] 次，则它内部贡献 C(cnt_v,2) = cnt_v(cnt_v-1)/2 个同值对。答案是 C(n,2) 减去所有值的 C(cnt_v,2)。

用桶统计 cnt，O(n + V) 一遍扫完，V 是值域 10^5。n = 10^5 时 C(n,2) ≈ 5×10^9，超出 int，必须用 long long。

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    const int V = 100000;
    vector<long long> cnt(V + 1, 0);
    for (int i = 0; i < n; i++) {
        int x; scanf("%d", &x);
        cnt[x]++;
    }
    long long ans = (long long)n * (n - 1) / 2;      // 全部有序对
    for (int v = 1; v <= V; v++) ans -= cnt[v] * (cnt[v] - 1) / 2;   // 减掉同值对
    printf("%lld\n", ans);
    return 0;
}

合法性其实是连通性条件。切掉 v 的全部绳索后，v 必然与房梁断开（其它宝石不能再断），所以操作合法 ⟺ 取走 v 之后，剩下的宝石仍然全部连到房梁。于是整个问题要求：每一步之后，剩余集合（加上房梁 0）都是连通的。

把顺序反过来：从集合 {0} 开始，按逆序把宝石一个个加回去。逆序里每次加入 v 时，剩下的是已经加进去的那些，所以要求恰好是「v 在已加入集合里有邻居」——加一个和当前集合相邻的点，连通性自动保持。这样做也把「割点」这类棘手判断完全绕开了。

正序要求每一步取的都是当前最大值，反过来就是要求加入顺序的价值不降。于是：所有宝石按价值升序处理，同价值的为一组；组内可以任意排序，因此只要组内某些点已经和已加入集合相邻，就可以先加它，再由它解锁同组别的点——也就是在组内做一次 BFS 扩散。

具体做法：排序后按价值分组；处理一组时，先把所有「已经与已加入集合相邻」的组内点入队，然后 BFS：出队即标记已加入，并把它在组内的邻居入队。整组扩散结束后若还有人没被加入，说明这个价值没法整体接上，答案 NO。

注意「只能取叶子」只是树上的特例。有环时，环上的点取走后其余部分仍连通，同样合法——样例 1 是个三角形，两个点都不是叶子却都能取，套「只取叶子」会直接错。

复杂度：排序 O(n log n)，BFS 每个点、每条边各走一次，总 O((n + m) log n)。

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

int main() {
    int n, m, k;
    if (scanf("%d %d %d", &n, &m, &k) != 3) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y; scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i + 1;
    sort(ord.begin(), ord.end(), [&](int x, int y) { return a[x] < a[y]; });   // 逆序 = 价值升序

    vector<char> added(n + 1, 0), inq(n + 1, 0), ing(n + 1, 0);
    added[0] = 1;                       // 房梁一开始就在集合里
    bool ok = true;
    int i = 0;
    while (i < n && ok) {
        int j = i;
        while (j < n && a[ord[j]] == a[ord[i]]) j++;         // 同价值一组
        for (int t = i; t < j; t++) ing[ord[t]] = 1;
        vector<int> q;
        for (int t = i; t < j; t++) {
            int v = ord[t];
            for (int w : g[v]) if (added[w]) { q.push_back(v); inq[v] = 1; break; }
        }
        for (size_t h = 0; h < q.size(); h++) {              // 组内扩散
            int v = q[h];
            added[v] = 1;
            for (int w : g[v]) if (ing[w] && !added[w] && !inq[w]) { inq[w] = 1; q.push_back(w); }
        }
        for (int t = i; t < j; t++) if (!added[ord[t]]) ok = false;   // 有人接不上
        for (int t = i; t < j; t++) ing[ord[t]] = 0;
        i = j;
    }
    puts(ok ? "YES" : "NO");
    return 0;
}