思路

维护红色节点的个数，需要维护二叉树中的每条链之间的影响， 影响分为两部分，第一部分是从上到下的影响，还是比如把9的子树涂红，之后再图9的子树中的节点比如18、19、36、72......等都不应该计算，这部分用一个哈希表存下之前出现过的所有点，再遍历当前节点的所有祖先，如果在表中出现了，就不计算当前节点了，因为祖先节点的个数是优先的，为 $log_2a_i$ 个，所以时间复杂度很低。

还有从下到上的影响，比如说将9的子树涂红之后，下次涂9的父节点4的时候就要少计算一部分，包括4的父节点2，2的父节点1都要少算一部分，这部分用一个哈希表存储所有的影响，同样因为祖先数很少，所以访问的节点数不多，可以保证时间复杂度。

计算子树中节点数量时先计算当前节点的子树的深度，就是总深度n减去当前节点的深度，从当前节点遍历到根节点即可，二叉树的节点数量为 $1+2+4+...+2^n = 2^{n-1}-1$。

代码

java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), q = sc.nextInt();
        Set<Long> mp1 = new HashSet<>();		//用于存储之前涂过的所有点
        Map<Long, Long> mp2 = new HashMap<>();	//用于存储每个点的子树中有多少点被涂完了
        long sum = 0;		//记录红色节点个数
        for (int i = 0; i < q; i++) {
            int deep = 0;
            long t = sc.nextLong();		//当前打算涂的节点
            for(long x = t; x != 0; x >>= 1){	//遍历当前节点的所有祖先节点
                if(mp1.contains(x)) {		//如果第一个哈希表中存在这个节点的祖先，当前节点就不需要处理，用deep作一下标记并退出循环
                    deep = -1;
                    break;
                }
                deep++;
            }
            if(deep == -1) {		//不需要处理当前节点
                System.out.println(sum);
                continue;
            }
            mp1.add(t);		//将当前节点存入第一个哈希表中
            long num = (1L << n-deep + 1) - 1;		//计算当前节点的子树节点个数
            if(mp2.containsKey(t)) num -= mp2.get(t);	//如果第二个哈希表中有当前节点，就减去之前已经涂过的节点个数
            for(long x = t; x != 0; x >>= 1){		//将当前涂的数量更新到第二个哈希表中
                if(mp2.containsKey(x))
                	mp2.put(x, num + mp2.get(x));
                else 
                	mp2.put(x, num);
            }
            sum += num;
            System.out.println(sum);
        }
    }
}

from collections import defaultdict
n , q = list(map(int,input().split()))
s = set()
cnt = defaultdict(int)
for _ in range (q):
	x = int(input())
	# 如果已经被覆盖，就不用了
	ok = True
	y = x 
	while y != 0:
		if y in s:
			ok = False
		y >>= 1
	if not ok:
		print (cnt[1])
		continue 
	# 加入集合
	s.add(x)
	# 计算深度
	dep = 0
	y = x
	while y != 0:
		dep += 1
		y >>= 1 
	# 满二叉的情况
	fv = (1 << (n - dep + 1)) - 1
	# 新增的个数
	delta = fv - cnt[x]
	# 更新祖先
	y = x
	while y != 0:
		cnt[y] += delta
		y >>= 1
	print (cnt[1])

题目内容

小红是一个热爱编程的大学生，他喜欢参加各种算法竞赛，挑战自己的智力。有一天，他在网上看到了一个有趣的二叉树问题，他决定尝试一下。他用纸和笔画出了一个 $n$ 层的满二叉树（共 $2^n-1$ 个节点，编号从 $1$ 到 $2^n-1$ ，对于编号为 $i$ （ $1 \le i\le 2^{n-1} -1$ ）的节点，它的左儿子为 $2*i$ ，它的右儿子为 $2*i+1$），然后用红色的笔操作 $q$ 次，每次都是在某些节点上画圈，表示将这些节点及其子树染红。他想知道每次染红后，二叉树中有多少个红色的节点。

他觉得这个问题很简单，只要用递归或者栈就可以解决。但是，当他开始编写代码时，他发现问题并没有那么容易。他需要考虑很多细节，比如如何存储和更新二叉树的状态，如何避免重复计算，如何优化时间和空间复杂度等等。他越写越觉得头疼，越写越觉得不对劲。他开始怀疑自己的能力，甚至怀疑这个问题是否有解。他不甘心放弃，他决定向你求助，希望你能给他一些提示或者思路。你能帮助小红吗？

输入描述

第一行输入两个正整数 $n$ 和 $q$ ，代表二叉树的层数和操作次数。

接下来的 $q$ 行，每行输入一个正整数 $a_i$ ，代表染色的节点编号。

$1\le n \le 40$

$1 \le q \le 10000$

$1 \le a_i \le 2^n$

输出描述

输出 $q$ 行，每行输入一个正整数，代表当前操作结束后二叉树的红色节点数量。

样例

输入

4 2
4
3

输出

3
10