猫树分治小记

2024-04-05 23:27:13

一个非常 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\) 的，劣于第一次做这道题时使用的前缀线性基做法，不过还是可以通过此题。

参考文献：

码农公寓

1. P6240 好吃的题目

2. CF1100F Ivan and Burgers

相关文章