3.22 阿里 技术类 笔试 第三题

给定一个n层的满二叉树，一共2^n-1个节点，编号从1到2^n-1。对于编号为i(1<=i<=2^n-1)的节点，它的左儿子为2i，它的右儿子为2i+1.有q次操作，每次操作我们选择一个节点a，将该节点a的子树的所有节点全部染红。每次操作后，你需要输出当前二女树红色节点的数量。

想法是维护一个优先队列，每次染色一个节点就查询该优先队列中是否包含该节点的祖先和子孙，如果包含祖先就不做操作，如果包含子孙要从总染色值中删除子孙的值。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n=in.nextInt();
            int q=in.nextInt();
            long sum=0;
            PriorityQueue<Long> pq=new PriorityQueue<>();
            for(int i=0;i<q;i++){
                long nodeid=in.nextInt();
                boolean hasParent=false;
                for(long elem:pq){
                    if(isParent(elem,nodeid)){
                        System.out.println("hasParent");
                        hasParent=true;
                        break;
                    }
                    else if(isParent(nodeid,elem)){
                        System.out.println("hasChild");
                        pq.remove(elem);
                        sum-=countNode(elem,n);
                    }
                }
                if(hasParent){
                    System.out.println("hasParent and sum="+sum);
                }else{
                    sum+=countNode(nodeid,n);
                    pq.add(nodeid);
                    System.out.println("noParent and sum="+sum);
                }
            }
            System.out.println();
        }
    }
    public static boolean isParent(long parent,long child){
        while(parent<=child){
            if(parent==child||parent*2==child||parent*2+1==child){
                return true;
            }
            parent*=2;
        }
        return false;
    }
    public static long countNode(long nodeid, int level){
        long cnt=1;
        long maxNodeId=(long)Math.pow(2,level)-1;
        long sum=0;
        while(nodeid<maxNodeId){
            sum+=cnt;
            nodeid*=2;
            cnt*=2;
        }
        return sum;
    }
}