题面叙述
题目给出两种操作： 操作1是将一个权重为W的点加到树的某个节点下。 操作2是询问一个从R开始的序列的最长可能长度。 其中这个序列要这样找：从R开始，沿着祖先方向往上找，凡是权重大于等于当前序列最后一个点的要被选上，然后更新序列。权重和要最大且小于X。
题解
我们设定一个数组nxt[i]表示i的祖先中，第一个权重大于等于i的权重的节点。再定义一个数组sum[i]表示从i出发，一直往上走所形成的满足题意序列的权重和，我们可以认为sum[i]是一个前缀和。 下面我们的关键是怎么来维护nxt数组和sum数组，如果新来一个R节点，把它放在U节点下面的话，怎么找到这条链上第一个权重大于等于R的权重的节点成了问题。 我们最直接想到的方法是暴力，一个一个往上枚举，但是这样复杂的显然会爆炸。所以我们用倍增的思想。即nxt[i][j]表示从i节点出发的满足题意的序列中距离i为
2j
2
j
的点的编号。 那么我们可以用二分搜索的方式快速的找到这条链上第一个权重大于等于R的权重的节点。时间复杂度
O((logn)2)
O
(
(
l
o
g
n
)
2
)
。 然后就得到了nxt[R][0]，
nxt[R][i]=upstep(nxt[R][0],2i−1)
n
x
t
[
R
]
[
i
]
=
u
p
s
t
e
p
(
n
x
t
[
R
]
[
0
]
,
2
i
−
1
)
其中upstep(u,s)表示由u开始，往上走s步到达的节点。 回答询问也很简单，同样适用二分答案的方式，二分序列的长度， 找到满足
sum[R]−sum[upstep(R,s)]<=X
s
u
m
[
R
]
−
s
u
m
[
u
p
s
t
e
p
(
R
,
s
)
]
<=
X
最大的s，s就是答案。时间复杂度同样是
O((logn)2)
O
(
(
l
o
g
n
)
2
)
。
代码
#include <cstdio>
#include <iostream>
typedef long long ll;
const int maxn =
400007;
const ll inf =
1e18;
ll ws[maxn],sum[maxn],nxt[maxn][
25],dep[maxn],p,q,Q,tp,last,cnt =
1;
int upstep(
int rt,
int step){
int i =
0;
int ans = rt;
while(step){
if(step&
1) ans = nxt[ans][i];
step >>=
1;
i++;
}
return ans;
}
void op1(){
ll R = last ^ p,W = last ^ q,U = ++cnt;
ws[U] = W;
if(ws[R] >= ws[U]) nxt[U][
0] = R;
else{
ll l =
1,r = (cnt+
1),mid,tar;
while(r-l>
1){
mid = (l+r)/
2;
tar = upstep(R,mid);
if(ws[tar] >= ws[U]) r = mid;
else l = mid;
}
tar = upstep(R,l);
if(ws[tar] >= ws[U]) nxt[U][
0] = tar;
else nxt[U][
0] = nxt[tar][
0];
}
sum[U] = sum[nxt[U][
0]] + W;
dep[U] = dep[nxt[U][
0]] +
1;
for(
int i =
1;i <
21;++i) nxt[U][i] = upstep(nxt[U][
0],(
1<<i)-
1);
}
void op2(){
ll R = last ^ p,X = last ^ q;
if(X < ws[R]){
printf(
"%lld\n",last =
0);
return ;
}
ll l =
1,r = dep[R]+
1,mid,tar,sm;
while(r-l>
1){
mid = (l+r)/
2;
tar = upstep(R,mid);
sm = sum[R] - sum[tar];
if(sm > X) r = mid;
else l = mid;
}
tar = upstep(R,l);
printf(
"%lld\n",last = l);
}
int main(){
dep[
1] =
1;
ws[
0] = inf;
scanf(
"%lld",&Q);
while(Q--){
scanf(
"%lld%lld%lld",&tp,&p,&q);
if(tp ==
1) op1();
else op2();
}
}
