猫树分治小记

一个非常 trivial 也不太常见的算法,不过学过了就不要忘了哦(

猫树问题可以适用于离线解决以下类型的数据结构问题:

  • 与序列有关,且询问是一段区间
  • 序列静态,即,不涉及修改操作

当然离不离线都可以,由于其过程类似于点分治,所以在线的情况可通过类似于建出建出点分治的情况动态维护。

首先我们总结一下,序列有关的静态区间询问问题有什么一般性的解决方法(注:下文中默认 \(n\) 为序列长度,\(q\) 为询问次数):

  • 如果贡献支持相减,如和/异或和,那么一遍前缀和即可搞定,时间复杂度 \(n+q\)​

  • 如果贡献不支持相减,但允许重复计算,如 \(\min,\max,\text{or},\text{and}\)​,那么有以下三种选择:

    • 线段树维护区间答案,\(\mathcal O(n+q\log n)\),缺点是回答询问复杂度多一个 \(\log\)。

    • ST 表预处理 + \(\mathcal O(1)\) 回答询问,\(\mathcal O(n\log n+q)\),缺点是空间太大。

    • 建出笛卡尔树 + \(\mathcal O(n)-\mathcal O(1)\) LCA,\(\mathcal O(n+q)\),缺点是 \(\mathcal O(n)-\mathcal O(1)\) LCA 普及率太低,没啥实用性

  • 如果贡献不能重复运算也不支持相减,但支持合并,那么只能线段树维护区间答案,\(\mathcal O(n+q\log n)\)

当然以上复杂度分析都是建立在合并两个答案的复杂度为 \(\mathcal O(1)\) 的基础上的,那么如果合并两个答案的复杂度不是 \(\mathcal O(1)\) 怎么办呢?如果我们记合并的复杂度为 \(T_{\text{merge}}(n)\),那么在上面的算法中,使用线段树维护区间的真实复杂度应是 \(n·T_{\text{merge}}(n)+q\log n·T_{\text{merge}}(n)\),使用 ST 表维护区间的真实复杂度应是 \(n\log n·T_{\text{merge}}(n)+q·T_{\text{merge}}(n)\)。如果 \(T_{\text{merge}}(n)\) 级别较高那我们的做法就不太适用了,那么有什么简便点的办法呢?这时候就要用到猫树分治了。

猫树分治的大致思想有点像整体二分,又有点像分治求满足 xxx 条件的区间个数的思想(如果不太明白怎样分治数区间可以见我 P5502 的题解,看我自己想出来的那个方法,或者 CF1175F 的题解中那个分治的解法,应该不至于看不明白罢,不会吧不会吧)。考虑分治区间 \([l,r]\) 时候将所有满足 \([L,R]\subseteqq [l,r]\) 的区间压入一个 vector。如果 \(l=r\) 那答案一般是比较好求的,直接算就行了。否则设 \(mid=\lfloor\dfrac{l+r}{2}\rfloor\),然后对于 \(i\in[l,mid]\) 扫一遍处理 \([i,mid]\) 的答案,再对于 \(i\in[mid+1,r]\) 也扫一遍处理 \([mid+1,i]\) 的答案,这样处理某个询问 \([L,R]\) 时:

  • 如果 \([L,R]\subseteqq[l,mid]\) 则把它放到左边区间的 vector 里递归
  • 如果 \([L,R]\subseteqq[mid+1,r]\)​ 则把它放到左边区间的 vector 里递归
  • 如果 \(L\in[l,mid],R\in[mid+1,r]\),则将 \([L,mid],[mid+1,R]\) 的答案合并即可。

不难发现,在上述做法中,我们通过分治把 \(\log\) 的复杂度和单次插入的复杂度摊到了一起,这样每次询问时只用合并一次。如果我们记插入的复杂度为 \(T_{\text{insert}}(n)\),那么上述算法的复杂度就是 \(n\log n·T_{\text{insert}}(n)+q·T_{\text{merge}}(n)\)。

当然如果强制在线也做得了,直接对于每一层分治记录下 \([i,mid],[mid+1,j]\) 的答案,这样可以做到强制在线,复杂度 \(n\log n·T_{\text{insert}}(n)+q\log n+q·T_{\text{merge}}(n)\),当然这样空间可能略有点危,如果记我们单个合并的信息的空间复杂度为 \(M(n)\),那么该做法空间复杂度为 \(n\log n·M(n)\)。

接下来看一些例子吧:

1. P6240 好吃的题目

模板题,上述过程中的结构换成背包即可,这样往背包中加入一个元素复杂度为 \(\mathcal O(V)\),合并两个背包复杂度也是 \(\mathcal O(V)\),总复杂度就是 \(n\log n·V+qV\)​,可以通过此题。

放个代码吧:

const int MAXN=4e4;
const int MAXQ=2e5;
const int MAXV=200;
int n,qu,h[MAXN+5],w[MAXN+5],res[MAXQ+5];
struct qry{int l,r,t;} q[MAXQ+5];
int pre[MAXN+5][MAXV+5],suf[MAXN+5][MAXV+5];
void solve(int l,int r,vector<int> cd){
	if(l==r){
		for(int id:cd) res[id]=(h[l]<=q[id].t)?w[l]:0;
		return;
	} int mid=l+r>>1;vector<int> nL,nR;
	for(int i=l;i<=r;i++) for(int j=0;j<=MAXV;j++)
		pre[i][j]=suf[i][j]=0;
	for(int i=mid;i>=l;i--){
		for(int j=0;j<=MAXV;j++) suf[i][j]=suf[i+1][j];
		for(int j=h[i];j<=MAXV;j++) chkmax(suf[i][j],suf[i+1][j-h[i]]+w[i]);
	}
	for(int i=mid+1;i<=r;i++){
		for(int j=0;j<=MAXV;j++) pre[i][j]=pre[i-1][j];
		for(int j=h[i];j<=MAXV;j++) chkmax(pre[i][j],pre[i-1][j-h[i]]+w[i]);
	}
	for(int id:cd){
		if(q[id].r<=mid) nL.pb(id);
		else if(q[id].l>mid) nR.pb(id);
		else{
			for(int i=0;i<=q[id].t;i++)
				chkmax(res[id],suf[q[id].l][i]+pre[q[id].r][q[id].t-i]);
		}
	} solve(l,mid,nL);solve(mid+1,r,nR);
}
int main(){
	scanf("%d%d",&n,&qu);vector<int> ini;
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	for(int i=1;i<=qu;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].t),ini.pb(i);
	solve(1,n,ini);
	for(int i=1;i<=qu;i++) printf("%d\n",res[i]);
	return 0;
}

2. CF1100F Ivan and Burgers

Yet another mol ban tea,把上文中的结构替换成线性基即可,仿照上一题的复杂度分析可知该做法复杂度是 \((n+q)\log^2n\) 的,劣于第一次做这道题时使用的前缀线性基做法,不过还是可以通过此题。

参考文献:

上一篇:react学习笔记04@TencentIT


下一篇:react生命周期和组件生命周期