zcmimi's blog

arrow_back静态链分治共7篇文章

avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树

avatar
zc
2020-03-01 19:36:00
查看原题

点击跳转

先离散化权值为排名,从大到小排序

遍历所有点,用权值树状数组统计,结果是 遍历完该子树后答案 - 遍历该子树前答案

(为什么一开始会去想什么dsu on tree和线段树合并

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

静态链分治

记得开long\ long

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

好题!

重新排序后能变成回文串,出现次数为奇数的字母最多只能有一种

因为只有22种字符所以我们可以用状态压缩来记录每种字母出现的次数是奇数或者偶数

设路径端点的两端为x,y,d_x表示1~x所有状态的异或值,D_x表示x的深度

那么如果这条路径满足条件,则d_x \oplus d_y在二进制下最多只有一个1

它的长度为D_x + D_y - 2 \times D_{lca(x,y)}

我们可以开一个桶来记录每种状态出现的最深的位置是哪里

sta为满足条件的状态

用每个店更新答案的时候就ans=\max(ans,b[sta \oplus d_x] + D_x - 2 \times D_{lca})

接下来就按静态链分治的套路操作就可以了

复杂度: \Theta( n \log n)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

静态链分治 参见模板

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

倍增找k级祖先+dsu on tree静态链分治

设当前节点为x

如果d_x < k,那么答案当然为0 可以找到第k级祖先,然后在k级祖先上添加一组询问(求它子树中深度为d_x的节点数)

因为这个还算上了x本身,所以把结果-1就是答案了

统计区间中各个深度的点有多少个就直接tot[d_x]+=(1\text{或}-1)就可以了

上代码:

1/1
Search
search