不懂就问

P1600 [NOIP2016 提高组] 天天爱跑步

sjwhsss @ 2024-11-25 20:30:48

为什么我自己写的线段树合并计算终点的贡献用

Insert(rt[y] , 1 , n<<1 , dep[x] - dep[lca] * 2 + n , 1);
Insert(rt[fa[lca]] , 1 , n<<1 , dep[x] - dep[lca] * 2 + n , -1);

ans[u]+=Query(rt[u] , 1 , n<<1 , w[u] - dep[u] + n);

就过不了样例二,而用题解的

Insert(rt[y] , 1 , n<<1 , n + dep[lca] * 2 - dep[x] , 1);
Insert(rt[fa[lca]] , 1 , n<<1 , n + dep[lca] * 2 - dep[x] , -1);

ans[u]+=Query(rt[u] , 1 , n<<1 , dep[u] - w[u] + n);

就能过,两个写法不是等价的吗?


by D_FANG @ 2024-12-09 16:53:40

@sjwhsss 可能……也许……大概……,在您的

dep[x] - dep[lca] * 2 + n

当树成一条链,lca为链末端时,这条式子好像会为0,但您的线段树的值域却是从1开始(但这好像和你过不了样例2没啥练习


by D_FANG @ 2024-12-09 16:54:10

说错了,是联系


|