自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 23:03:14，当前版本为作者最后更新于2024-10-02 16:45:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

审题

这里有一个完全二叉树。

分析

首先，根据题目可知，这是一个完全二叉树，因此可知深度不超过 $20$。再看 $q$ 的大小，$1 \le q \le 2 \times 10^5$，由此可知，在询问中可以跑树的深度。
而树的深度就可以找祖先节点。
类型一：标记颜色，根据 $y$ 的大小，给一路上的祖先节点染色。
类型二：寻找颜色，在一路上的祖先节点中找到最后染色，且能给他染色。
详见代码。

100分代码

#include<bits/stdc++.h>
using namespace std;
int z[1000005];
int c[1000005][55];
void sign(int x,int d,int nu){
	c[x][d]=nu;
	if(x==1||d==0) return ;
	sign(x/2,d-1,nu);
}
int find(int x,int step){
	if(x==0) return 0;
	int maxn=0;
	for(int i=step;i<=54;i++){
		maxn=max(maxn,c[x][i]);
	}
	return max(maxn,find(x/2,step+1));
}
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y;
			cin>>x>>y>>z[i];
			if(y>54)y=54;
			sign(x,y,i);
		}
		else{
			int x;
			cin>>x;
			cout<<z[find(x,0)]<<"\n";
		}
	}
	return 0; 
}