题目
见链接。
题解
知识点：倍增。
注意到，题目其实要求我们，每次要选最近一个权值大于等于自己的祖先，可以看出固定点生成出来的序列是固定的。因此，考虑设 \(f_{i,j}\) 为从 \(j\) 出发按规则向上走 \(2^i\) 次的点，设 \(b_{i,j}\) 为从 \(j\) 出发按规则向上走 \(2^i\) 次的所有序列点的权值和。
对于查询，需要注意要手动避免越界的 \(0\) 号节点问题，其余和正常倍增一致。
对于修改，由于是尾部追加，因此倍增可以支持，需要先确定向上第一个点是谁：
- 若新加点比它父亲小，那么直接设为它父亲。
- 否则，从父亲出发生成的序列中，找到比自己大的第一个点，显然可以用倍增找到。
随后更新一下倍增数组即可。
时间复杂度 \(O(Q \log Q)\)
空间复杂度 \(O(Q \log Q)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 400007;
int cnt;
int a[N];
int f[27][N];
ll b[27][N];
void update(int u, ll w) {
a[++cnt] = w;
if (a[u] >= a[cnt]) {
f[0][cnt] = u;
b[0][cnt] = a[u];
}
else {
for (int i = 20;i >= 0;i--) {
if (!f[i][u]) continue;
if (a[f[i][u]] < a[cnt]) u = f[i][u];
}
f[0][cnt] = f[0][u];
b[0][cnt] = a[f[0][u]];
}
for (int i = 1;i <= 20;i++) {
f[i][cnt] = f[i - 1][f[i - 1][cnt]];
b[i][cnt] = b[i - 1][cnt] + b[i - 1][f[i - 1][cnt]];
}
}
int get_ans(int u, ll k) {
if (a[u] > k) return 0;
int ans = 1;
ll sum = a[u];
for (int i = 20;i >= 0;i--) {
if (!f[i][u]) continue;
if (sum + b[i][u] <= k) {
sum += b[i][u];
ans += 1 << i;
u = f[i][u];
}
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
++cnt;
int Q;
cin >> Q;
ll last = 0;
while (Q--) {
int op;
ll p, q;
cin >> op >> p >> q;
if (op == 1) {
int r = p ^ last;
ll w = q ^ last;
update(r, w);
}
else {
int r = p ^ last;
ll x = q ^ last;
cout << (last = get_ans(r, x)) << '\n';
}
}
return 0;
}