题解：P12359 [eJOI 2024] 古迹漫步 / Old Orhei

· · 题解

直接暴力查询复杂度是 O(Q\times T)，考虑优化。

发现点的数量很少，并且序列 \texttt{A} 中对多个连续段操作可以合并成一次操作。考虑用线段树进行优化。我们用线段树节点维护序列 \texttt{A} 中的一个区间 [l, r]，表示从某个点出发，经过 \texttt{A} 序列中的这段区间可以到达哪个点。如果第 i 个点经过 A_l,A_{l+1},...,A_x 操作后可以到达 j，经过 A_x,A_{x+1},...,A_r 操作后可以到达 k，则 i 可以经过 A_l,...,A_r 操作直接到达 k，将节点信息向上更新即可。 

struct Road {
    int u, v; // A_u \sim A_v
} rd[N];
struct Tree {
    int l, r;
    int to[105];
} tree[N << 2];
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void PushUp(int p) {
    for (int i = 1; i <= n; i++) {
        tree[p].to[i] = tree[rs(p)].to[tree[ls(p)].to[i]];
    }
}
void Build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    if (tree[p].l == tree[p].r) {
        for (int i = 1; i <= n; i++) tree[p].to[i] = i;
        tree[p].to[rd[a[l]].u] = rd[a[l]].v;
    } else {
        int mid = (tree[p].l + tree[p].r) >> 1;
        Build(ls(p), l + 0, mid);
        Build(rs(p), mid + 1, r);
        PushUp(p);
    }
}
void Change(int p, int x, int d) {
    if (tree[p].l == tree[p].r) {
        for (int i = 1; i <= n; i++)  tree[p].to[i] = i;
        tree[p].to[rd[d].u] = rd[d].v;
    } else {
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (x <= mid)Change(ls(p), x, d);
        if (mid < x) Change(rs(p), x, d);
        PushUp(p);
    }
}
int Ask(int p, int l, int r, int s) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].to[s];
    } else {
        int res = s;
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (l <= mid) res = Ask(ls(p), l, r, res);
        if (mid < r)  res = Ask(rs(p), l, r, res);
        return res;
    }
}
/*====================*/
void Solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        rd[i].u = u;
        rd[i].v = v;
    }
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> a[i];
    }
    Build(1, 1, t);
    cin >> q;
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            int s; cin >> s;
            cout << Ask(1, l, r, s) << endl;
        } else {
            Change(1, l, r);
        }
    }
    return;
}