2026 WUST选拔赛Round1 L题题解#

原题链接：Nowcoder

题意：#

在 $1$ 到 $n$ 上有 $n$ 个位置，每个位置放置了一个弹簧，弹簧能将弹球弹到固定的点 $a[i]$ $(1 \leq a[i] \leq n)$ 上。

接下来要进行 $m$ 个操作：在第 $i$ $(1 \leq i \leq m)$ 个操作中，你需要放置一个拥有无限动力的弹球在 $b[i] \oplus c[i - 1]$ 处，并回答在 $b[i] \oplus c[i - 1]$ 处的弹球个数 $c[i]$ 。

注意：操作的顺序为：先放入一个弹球，询问当前位置的弹球数量，再所有弹球沿边移动一步。

已知 $c[0] = 0$ 。给定位置个数 $n$ $(1 \leq n \leq 5e5)$ ，操作数 $m$ $(1 \leq m \leq 5e5)$ 和数组 $a$ ， $b$ 。保证所有弹球都会被放置在 $pos$ $(1 \leq pos \leq n)$ 中。

思路：#

转化题意

由于每个位置的弹球都会在一次操作中从位置 $x$ 被移到 $a[x]$ ，因此可以将每一个位置看成一个点，并连接一条有向边，形成了由若干个基环树组成的函数图。因此，此题可以转化为：在由若干个基环树组成的函数图上，支持动态加入弹球，并在线查询某个时刻某个点上的弹球数量。
非环点

对于不在环上的点，弹球会不断沿边移动，直到第一次到达唯一的，且在其所在基环树的环上的点为止。对于任意一个基环树来说，每一个非环点都在以某个唯一的，且在其所在基环树的环上的点为根的树上。因此，我们可以建立反图，利用树的结构去维护位置。

接下来需要维护非环点上弹球的位置。设在第 $t$ 次操作中在非环点 $u$ 放入弹球，在第 $i$ $(t \leq i \leq m)$ 次操作中询问非环点 $v$ ，且这个弹球在点 $v$ 上。利用树的结构，我们可以知道弹球从 $u$ 移动到点 $v$ 所需要的时间为点 $u$ 在树上的深度减去 $v$ 的在树上的深度，设 $dep[x]$ 表示点 $x$ 的深度，即有： $i - t = dep[u] - dep[v]$ ，变形可以得到： $i + dep[v] = t + dep[u]$

另外，点 $u$ 一定位于以点 $v$ 为根的子树中。因此，不仅要满足 $i + dep[v] = t + dep[u]$ 的时间条件，也要满足路径条件。可以对每一个树都维护一个 $dfs$ 序，设点 $tin[x]$ 和 $tout[x]$ 分别为点 $x$ 的 $dfs$ 进入时间和点 $x$ 子树内最大的 $dfs$ 进入时间，则需满足： $tin[v] \leq tin[u] \leq tout[v]$

因此，查询非环点 $v$ 时，只需统计满足 $i + dep[v] = t + dep[u]$ 且 $tin[u]$ 在 $[tin[v], tout[v]]$ 之间的历史插入点 $u$ 。因此，可以按照 $key$ $(key = t + dep[u])$ 的值进行分类，对于每一个 $key$ 来说，使用对应的平衡树维护其插入点的 $dfs$ 序，并统计 $[tin[v], tout[v]]$ 之间的数目即可。我们可以使用unordered_map<int, ordered_set<array <int, 2> >进行维护。其中 $key = t + dep[u]$ ，ordered_set中存储 {tin[u], t} ，防止同一个点多次插入后仍计算为同一个点。
环点

对于环上的点，弹球会不断沿环上的边移动。设在第 $t$ 次操作中在环点 $u$ 放入弹球，环点 $u$ 所在的环的长度为 $len$ ，环点编号为 $pos_i$ 。则在第 $T$ $(t \leq T \leq m)$ 次操作中，弹球会移动到编号为 $pos[v]$ $(pos[v] \equiv pos[u] + (T - t) \pmod {len})$ 上，变形有： $pos[u] - t \equiv pos[v] - T \pmod {len}$

因此，与非环点类似， $pos[u] - t$ 仍然是一个不变量 $c\_id$ ，利用简单数组统计有相同 $c\_id$ 的点的数量即可。

除此之外，环点还需要维护弹球从非环点走到环上的弹球数量。对于每一个在非环点的弹球，可以利用其树的深度来快速算出其进入环点的时间，可以在对应的时间把这些点当作环点加入环内即可。

代码：#

1
#include <bits/stdc++.h>
2
#include <bits/extc++.h>
3
using namespace std;
4
using namespace __gnu_pbds;
5
#define int long long
6
template <typename T>
7
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
8
using arr2 = array <int, 2>;
9

10
void solve ()
11
{
12
    int n;
13
    cin >> n;
14
    vector <int> a(n + 1), ind(n + 1);
15
    vector <vector <int> > rev(n + 1);
16

17
    for (int i = 1; i <= n; i++) {
18
        cin >> a[i];
19
        ind[a[i]]++;
20
        rev[a[i]].push_back(i);
21
    }
22

23
    // 一.建基环树
24
    // 1.topo判环
25
    vector <int> removed(n + 1);
26
    queue <int> q;
27
    for (int i = 1; i <= n; i++) {
28
        if (ind[i] == 0) {
29
            q.push(i);
30
        }
31
    }
32

33
    while (!q.empty()) {
34
        auto u = q.front();
35
        q.pop();
36
        removed[u] = true;
37
        int v = a[u];
38
        if (--ind[v] == 0) q.push(v);
39
    }
40

41
    // 2.建环
42
    vector <vector <int> > cycle;
43
    vector <int> vis(n + 1, 0);
44
    int id = 0;
45
    for (int i = 1; i <= n; i++) {
46
        if (removed[i] || vis[i]) continue;
47
        vector <int> cyc;
48
        int u = i;
49
        while (!vis[u]) {
50
            vis[u] = 1;
51
            cyc.push_back(u);
52
            u = a[u];
53
        }
54
        cycle.push_back(cyc);
55
    }
56

57
    // 3.初始化树的信息
58
    vector <int> comp(n + 1), pos(n + 1), dep(n + 1), root(n + 1);
59
    int sum_cyc = cycle.size();
60

61
    for (int id = 0; id < sum_cyc; id++) {
62
        for (int i = 0; i < cycle[id].size(); i++) {
63
            int u = cycle[id][i];
64
            comp[u] = id;
65
            pos[u] = i;
66
            dep[u] = 0;
67
            root[u] = u;
68
        }
69
    }
70

71
    // 4.建反树
72
    vector <vector <int> > e(n + 1);
73
    for (int u = 1; u <= n; u++) {
74
        for (auto v : rev[u]) {
75
            if (removed[v]) {
76
                e[u].push_back(v);
77
            }
78
        }
79
    }
80

81
    // 5.求dfs序
82
    vector <int> tin(n + 1), tout(n + 1);
83
    int time = 0;
84

85
    auto dfs = [&] (auto self, int u) -> void {
86
        tin[u] = ++time;
87
        for (auto v : e[u]) {
88
            comp[v] = comp[u];
89
            root[v] = root[u];
90
            dep[v] = dep[u] + 1;
91
            self(self, v);
92
        }
93
        tout[u] = time;
94
    };
95

96
    for (auto &cyc : cycle) {
97
        for (auto r : cyc) {
98
            dfs(dfs, r);
99
        }
100
    }
101

102
    // 二.计算答案
103

104
    // 1.初始化
105
    int m;
106
    cin >> m;
107
    vector <int> len(sum_cyc);
108
    vector <vector <int> > cyc_info(sum_cyc);
109
    for (int id = 0; id < sum_cyc; id++) {
110
        len[id] = cycle[id].size();
111
        cyc_info[id].assign(len[id], 0);
112
    }
113

114
    vector <vector <arr2> > update(m + 1);
115
    unordered_map <int, ordered_set<arr2> > mp;
116
    mp.reserve(m * 2 + 10);
117

118
    int pre = 0;
119

120
    for (int i = 1; i <= m; i++) {
121
        for (auto [id, c_id] : update[i]) {
122
            cyc_info[id][c_id]++;
123
        }
124
        int x;
125
        cin >> x;
126
        x = (x ^ pre);
127

128
        // 2.插入
129
        if (!removed[x]) {
130
            int id = comp[x];
131
            int c_id = ((pos[x] - i) % len[id] + len[id]) % len[id];
132
            cyc_info[id][c_id]++;
133
        }else {
134
            int key = i + dep[x];
135
            mp[key].insert({tin[x], i});
136
            int T = i + dep[x];
137
            if (T <= m) {
138
                int id = comp[x];
139
                int c_id = ((pos[root[x]] - T) % len[id] + len[id]) % len[id];
140
                update[T].push_back({id, c_id});
141
            }
142
        }
143

144
        // 3.查询
145
        int res = 0;
146
        if (!removed[x]) {
147
            int id = comp[x];
148
            int c_id = ((pos[x] - i) % len[id] + len[id]) % len[id];
149
            res = cyc_info[id][c_id];
150
        }else {
151
            int key = i + dep[x];
152
            auto it = mp.find(key);
153
            if (it != mp.end()) {
154
                auto &st = it->second;
155
                res = st.order_of_key({tout[x] + 1, -1}) - st.order_of_key({tin[x], -1});
156
            }
157
        }
158

159
        cout << res << '\n';
160
        pre = res;
161
    }
162
}
163

164
int32_t main ()
165
{
166
    ios::sync_with_stdio(false);
167
    cin.tie(nullptr);
168
    int _ = 1;
169
    // cin >> _;
170
    while (_--) {
171
        solve();
172
    }
173
    return 0;
174
}