不懂就问
查看原帖
不懂就问
982518
sjwhsss楼主2024/11/25 20:30

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

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);

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

2024/11/25 20:30
加载中...