题目详细题解

一、题目核心分析

1. 转账条件拆解

用户 $i$ 能向 $j$ 转账需满足3个核心条件：

1. 顺序限制：$i < j$
2. 标识符限制：$a_i < a_j$
3. 中间交易规则：
   • 存在中间序列 $i=x_1<x_2<\dots<x_k=j$
   • 相邻下标增幅不超过 $d$：$x_{t+1}-x_t \le d$
   • 中间标识符严格小于起点：$a_{x_t} < a_i$（$2\le t\le k-1$）

2. 问题目标

• 若 $t=1$：仅判断 $u \to v$ 是否可转账
• 若 $t=2$：求 $u \to v$ 转账的最少直接转账次数

3. 关键转化

• 先预处理：将标识符离散化，$rev[val]$ 表示标识符为 $val$ 的用户下标
• 对每个用户 $i$，预处理 $maxr[i]$：从 $i$ 出发，下标不超过 $i+d$ 且标识符最大的用户下标（这是单次转账能到达的最远位置）
  • 用有序集合 active 维护未被“覆盖”的下标，遍历标识符从小到大的用户，动态维护 $maxr[i]$

二、算法核心思路

1. 整体框架：分治+线段树

采用值域分治结合线段树的策略，核心逻辑：

1. 按标识符值域 $[0,n)$ 分治
2. 对每个分治区间，用线段树维护下标信息，快速查询最大/最小下标
3. 递归处理子区间，合并答案

2. 核心数组定义

3. 分治逻辑（divide 函数）

• 终止条件：区间长度 $\le 30$，暴力枚举计算答案
• 拆分：
  • 若起点 $u$ 标识符 $< m$：划入左子区间 $[l,m)$
  • 若终点 $v$ 标识符 $\ge m$：划入右子区间 $[m,r)$
  • 其余（跨中点）划入临时区间 $tmp$
• 处理临时区间：
  1. 左区间用线段树查询 $max\_jump[i]$（最大合法转移下标）
  2. 右区间用线段树查询 $min\_jump[i]$（最小合法转移下标）
  3. 用并查集路径压缩合并转移次数，累加得到总次数
• 递归：处理左右子区间的查询

三、代码逐段解析

1. 线段树工具类

struct segtree {
    vector<pii> tree;
    int sz;

    segtree() {}

    segtree(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        tree.resize(2 * sz, { inf, -inf }); // {min_val, max_val}
    }

    void pull(int v) { // 向上合并
        tree[v].first = min(tree[v<<1].first, tree[v<<1|1].first);
        tree[v].second = max(tree[v<<1].second, tree[v<<1|1].second);
    }

    void set(int i, int x) { // 单点赋值
        i += sz;
        tree[i] = {x, x};
        for (i >>= 1; i; i >>= 1) pull(i);
    }

    void set0(int i) { // 单点重置为无穷
        i += sz;
        tree[i] = {inf, -inf};
        for (i >>= 1; i; i >>= 1) pull(i);
    }

    int getmin(int l, int r) { // 区间查最小值
        int res = inf;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = min(res, tree[l++].first);
            if (r&1) res = min(res, tree[--r].first);
        }
        return res;
    }

    int getmax(int l, int r) { // 区间查最大值
        int res = -inf;
        for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = max(res, tree[l++].second);
            if (r&1) res = max(res, tree[--r].second);
        }
        return res;
    }
};

• 线段树每个节点存储区间最小下标和区间最大下标
• 支持单点更新、区间最值查询，时间复杂度 $O(\log n)$

2. 路径压缩函数

void compress(int a) {
    if (pr[a] == a) return;
    compress(pr[a]); // 递归压缩父节点
    len[a] += len[pr[a]]; // 累加转移次数
    pr[a] = pr[pr[a]]; // 路径压缩
}

• 并查集路径压缩优化，将链式转移摊平为直接跳转
• 累加 $len[a]$ 得到从 $a$ 到根节点的总转账次数

3. 分治核心函数（divide）

void divide(int l, int r, vector<query> q) {
    if (q.empty()) return;
    if (r - l <= 30) { // 小区间暴力
        // 预处理max_jump
        for (int val = l; val < r; val++) bucq[rev[val]].clear();
        for (auto &qi : q) bucq[qi.u].emplace_back(qi.v, qi.i);
        for (int val = l; val < r; val++) max_jump[rev[val]] = val;
        // 枚举区间内所有起点，暴力转移
        for (int lim = l; lim < r; lim++) {
            int u = rev[lim];
            for (int val = l; val <= lim; val++) {
                int i = rev[val];
                if (i <= u && u <= maxr[i]) max_jump[i] = lim;
            }
            // 处理该区间的查询
            for (auto &qi : bucq[u]) {
                int v = qi.first, idx = qi.second;
                while (v != u) {
                    if (max_jump[v] == a[v]) { // 无法转移
                        ans[idx] = -1;
                        break;
                    }
                    ans[idx]++; // 转账次数+1
                    v = rev[max_jump[v]]; // 跳转到下一个节点
                }
            }
        }
        return;
    }
    // 分治拆分
    int m = (l + r) / 2;
    // 重置临时数组
    for (int val = l; val < r; val++) {
        int i = rev[val];
        block[i].clear(); bucq[i].clear();
        len[i] = 0; pr[i] = i; no_jumps[i] = 0;
    }
    vector<query> ql, qr, tmp;
    // 划分查询到不同区间
    for (auto &qi : q) {
        if (a[qi.u] < m) ql.push_back(qi);
        else if (a[qi.v] >= m) qr.push_back(qi);
        else tmp.push_back(qi);
    }
    q.clear();
    if (!tmp.empty()) { // 处理跨中点查询
        // 左区间查询max_jump
        for (int val = l; val < m; val++) st.set(rev[val], val);
        for (int val = l; val < m; val++) {
            int i = rev[val];
            max_jump[i] = st.getmax(i, maxr[i] + 1);
        }
        for (int val = l; val < m; val++) st.set0(rev[val]);
        // 右区间查询min_jump
        for (int val = m; val < r; val++) st.set(rev[val], val);
        for (int val = l; val < m; val++) {
            int i = rev[val];
            min_jump[i] = st.getmin(i, maxr[i] + 1);
            if (min_jump[i] == inf) { // 无有效转移
                if (max_jump[i] == val) no_jumps[i] = 1;
                else {
                    pr[i] = rev[max_jump[i]];
                    len[i] = 1;
                }
            } else {
                block[min_jump[i]].push_back(i);
            }
        }
        // 收集查询
        for (auto &qi : tmp) bucq[qi.u].emplace_back(qi.v, qi.i);
        // 倒序处理右区间
        for (int val = r - 1; val >= m; val--) {
            int u = rev[val];
            for (auto &qi : bucq[u]) {
                int v = qi.first, idx = qi.second;
                if (no_jumps[v] && min_jump[v] > val) {
                    ans[idx] = -1;
                    continue;
                }
                compress(v); // 路径压缩
                ans[idx] += len[v]; // 累加次数
                v = pr[v];
                // 查询下一个转移节点
                int to = st.getmax(v, maxr[v] + 1);
                if (to == -inf) ans[idx] = -1;
                else {
                    ans[idx]++;
                    to = rev[to];
                    if (to != u) qr.emplace_back(to, u, idx);
                }
            }
            st.set0(u);
            // 合并block中的节点
            for (int i : block[val]) {
                if (!no_jumps[i]) {
                    pr[i] = rev[max_jump[i]];
                    len[i] = 1;
                }
            }
        }
    }
    // 递归处理子区间
    divide(l, m, ql);
    divide(m, r, qr);
}

4. 主函数与预处理

void solve() {
    int n, D, group;
    cin >> n >> D >> group;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--; // 标识符转0-based
        rev[a[i]] = i; // 建立映射
    }
    st = segtree(n);
    int queries; cin >> queries;
    vector<query> q;
    for (int i = 0; i < queries; i++) {
        int t, v, u; cin >> t >> v >> u;
        need_dist[i] = (t > 1); // 标记是否需要求次数
        v--; u--; // 转0-based
        if (a[v] > a[u]) ans[i] = -1; // 标识符不满足，直接不可达
        else q.emplace_back(v, u, i);
    }
    // 预处理maxr[i]
    set<int> active;
    for (int i = 0; i < n; i++) active.insert(i);
    for (int val = 0; val < n; val++) {
        int i = rev[val];
        // 移除下标超过i+D的元素
        while (true) {
            auto it = active.lower_bound(i);
            if (it == active.end() || *it >= i + D) break;
            active.erase(it);
        }
        // 确定maxr[i]
        auto it = active.lower_bound(i);
        maxr[i] = (it == active.end()) ? n - 1 : *it;
    }
    // 分治处理查询
    divide(0, n, q);
    // 输出答案
    for (int i = 0; i < queries; i++) {
        if (ans[i] == -1) cout << "0\n";
        else cout << (need_dist[i] ? ans[i] : 1) << '\n';
    }
}

• 预处理 $maxr[i]$：用有序集合 active 维护未被覆盖的下标，遍历标识符从小到大的用户，动态剔除下标超过 $i+D$ 的元素，得到每个用户能转移的最远下标
• 分治执行：调用 divide(0, n, q) 处理所有查询
• 结果输出：根据 need_dist 标记，输出是否可达（0/1）或最少转账次数

四、复杂度分析

1. 预处理 $maxr[i]$：有序集合操作均为 $O(\log n)$，总复杂度 $O(n \log n)$
2. 分治过程：
   • 每层分治处理所有查询，总操作 $O(n \log n)$
   • 线段树操作 $O(\log n)$，路径压缩均摊复杂度 $O(\alpha(n))$
   • 总时间复杂度 $O(n \log n + q \log n)$，其中 $q$ 为查询次数
3. 空间复杂度：$O(n)$，主要为数组、线段树和集合存储

五、核心逻辑总结

1. 预处理：通过有序集合快速计算每个用户的最远转移下标 $maxr[i]$
2. 值域分治：按标识符值域拆分查询，分别处理子区间和跨区间查询
3. 线段树+并查集：用线段树快速查询合法转移下标，用并查集路径压缩优化转移次数统计
4. 结果输出：根据查询类型，输出是否可达或最少转账次数