题解：P10990 [蓝桥杯 2023 国 Python A] 彩色二叉树

Clare613 · 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; 
}