【无标题】

题目
题意:
牛牛有一颗包含 nn 个结点的二叉树，这些结点编号为 1…n1…n 。这颗树被定义为：
1、以结点 1 为根。
2、编号为 xx 结点的两个儿子编号分别为： 2\times x2×x 和 2\times x + 12×x+1。
3、每个结点的权重初始都为 0。

牛牛接下来会对这颗树进行 mm 次操作，操作的格式是以下四种之一：
1、op\ xop x （这里 op = 1op=1 ）代表牛牛将以编号 xx 为根结点的子树中所有结点的权重 +1。
2、op\ xop x （这里 op = 2op=2 ）代表牛牛将以编号 xx 为根结点的子树外的所有结点权重 +1。
3、op\ xop x （这里 op = 3op=3 ）代表牛牛将根结点到编号 xx 结点的路径上的所有结点权重 +1。
4、op\ xop x （这里 op = 4op=4 ）代表牛牛将根节点到编号 xx 结点的路径上的结点之外的所有结点权重 +1。

牛妹想知道当牛牛的所有操作结束之后，树中权重为 0,1,2…m0,1,2…m 的结点的数量分别是多少。
思路: 没有思路。树上差分。操作1可以只对某个点操作，dfs时把父节点的贡献累加到当前节点即可；操作2可以等价于对整棵树++，对这棵树–。操作3则是dfs时把子节点的贡献累加到当前节点，因为选了某个点，相当于把叶子当根的1操作，子节点的贡献自然都要算上，操作4同理先整棵树++再对这条路径–.
代码:

#include
using namespace std;
const int N = 1e7+10;
typedef long long ll;
int n,m,k,T;
int s[N],s2[N<<1];
int f[N],f2[N]; //操作1、3
int cnt[int(5e5)+10];
int tot = 0; //整棵树
void dfs(int cur,int fa)
{
	if(cur>n) return ;
	s[cur] = s[fa] + f[cur];
	dfs(cur<<1,cur);
	dfs(cur<<1|1,cur);
	s2[cur] = s2[cur<<1]+s2[cur<<1|1]+f2[cur];
}
void solve()
{
	cin>>n>>m;
    int _ = m;
	while(_--)
	{
		int op; int x; cin>>op>>x;
		if(op==1)
		{
			f[x]++;
		}
		else if(op==2)
		{
			f[x]--; tot++;
		}
		else if(op==3)
		{
			f2[x]++;
		}
		else f2[x]--,tot++;
	}
	dfs(1,0);
	for(int i=1;i<=n;++i)
	{
		cnt[s[i]+s2[i]+tot]++;
		// cout<
	}
	for(int i=0;i<=m;++i)
	{
		cout<<cnt[i]<<" ";
	}
}
signed main(void)
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
	// cin>>T;
	while(T--)
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58