题解：P5889 跳树

分析

题目总共的三种操作都很格式，每个点也没有什么特别之处，所以只需要考虑当前位置位移即可。二叉树的位移正好可以使用位运算实现：

位移至左儿子，即 root<<1。
位移至右儿子，即 root<<1|1。
位移至父亲节点，即 root>>1。

综合起来，每一个点都进行运算的话，每一个回答都可以写成 (sum>>down)<<up|val，所以只需要维护区间的值即可。修改操作为单点修改，将一个操作修改为另一个操作。如果要暴力维护的话就是

\operatorname{O}(n^2)

的复杂度。所以考虑使用线段树维护，复杂度

\operatorname{O}(n\log n)

。

合并操作

合并操作是这道题目第一大难题。

首先需要确定线段树中维护的东西：

向上跳的次数。
向下跳的层数（因为不确定是往左还是往右，所以只能够说是层数）。
在向下的层数中，目标节点和最左端节点的偏差。

观察可得，每向下跳一次并且跳在了右子节点上，偏差就会翻倍并且加上从相邻左子节点到目标右子节点的数量，即 val=val<<1|1，其实就是往右的下标。第一次，找到这一个或上的

1

，之后不断这样操作即可。

同时，向上的数量永远可以抵消向下的数量，但是向下的数量不一定能够抵消向上的数量，所以就需要这一个 val 来平衡。

其他的没什么了，因为这一个合并操作满足可加性，并且题目中的需求是单点修改和区间查询，所以使用线段树来维护。

代码

CPP

#include<bits/stdc++.h>
#define MAXN 500001
#define push_up(root) tree[root]=merge(tree[root<<1],tree[root<<1|1])
#define debug(node) cout<<node.up<<" "<<node.down<<" "<<node.val<<endl
typedef long long ll;
using namespace std;
struct node{
	int up,down;
	ll val;
//	node()=default;
	node(int up=0,int down=0,ll val=0ll){
		this->up=up;
		this->down=down;
		this->val=val;
	}
}tree[MAXN<<2];
int m,q,op[MAXN];
inline node set_opt(int opt){
    if(opt==1){
    	return node(1,0,0ll);
	}else if(opt==2){
		return node(1,0,1ll);
	}
	return node(0,1,0ll);
}
inline node merge(node lson,node rson){
	node result;
	result.val=(lson.val>>rson.down)<<rson.up|rson.val;
	result.down=lson.down+max(rson.down-lson.up,0);
	result.up=rson.up+max(lson.up-rson.down,0);
	return result;
}
inline void build(int root,int l,int r){
	if(l==r){
		tree[root]=set_opt(op[l]);
//		debug(tree[root]);
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	push_up(root); 
//	debug(tree[root]);
}
inline node query(int root,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tree[root];
	}
	int mid=(l+r)>>1;
	node result;
	if(L<=mid){
		result=merge(result,query(root<<1,l,mid,L,R));
	}
	if(mid<R){
		result=merge(result,query(root<<1|1,mid+1,r,L,R));
	}
//	debug(result);
	push_up(root);
	return result;
}
inline void change(int root,int pos,int l,int r,int opt){
	if(pos==l&&pos==r){
		tree[root]=set_opt(opt);
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		change(root<<1,pos,l,mid,opt);
	}else{
		change(root<<1|1,pos,mid+1,r,opt);
	}
	push_up(root);
}
int main(){
	scanf("%*d %d %d",&m,&q);
	for(int i=1;i<=m;++i){
		scanf("%d",&op[i]);
	}
	build(1,1,m);
	while(q--){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			ll s;
			int l,r;
			scanf("%lld %d %d",&s,&l,&r);
			node result=query(1,1,m,l,r);
//			debug(result);
			printf("%lld\n",max(1ll,s>>result.down)<<result.up|result.val);
		}else{
			int x,y;
			scanf("%d %d",&x,&y);
			change(1,x,1,m,y);
		}
	}
	return 0;
}
/*
3 5 4
1 2 3 3 1
1 3 4 5
1 2 2 4
2 3 1
1 1 2 3
*/

文章操作

分析

合并操作

代码

相关推荐

评论

题解：P5889 跳树