剖分(树形差分)

E-剖分_牛客小白月赛62 (nowcoder.com)

题目描述
牛牛有一颗包含n个结点的二叉树，这些结点编号为1 ...n。这颗树被定义为:1、以结点1为根。
2、编号为α结点的两个儿子编号分别为:2 xa和2×巴+ 1。3、每个结点的权重初始都为0。
牛牛接下来会对这颗树进行m次操作，操作的格式是以下四种之—:
1、op a(这里op = 1）代表牛牛将以编号α为根结点的子树中所有结点的权重+1。

2、op c(这里op = 2)    代表牛牛将以编号α为根结点的子树外的所有结点权重+1。

3、op a(这里op = 3）代表牛牛将根结点到编号α结点的路径上的所有结点权重+1。
4、op a:(这里op= 4)代表牛牛将根节点到编号α结点的路径上的结点之外的所有结点权重+1。
牛妹想知道当牛牛的所有操作结束之后，树中权重为0,1,2 . ..m 的结点的数量分别是多少。
输入描述:
第一行输入两个空格分隔的整数: n m。
接下来 m行，每行描述了一个牛牛进行的操作。保证:
0 输出描述:
输出一行共m＋1个整数，代表答案。

输入

复制7 4 1 2 3 5 4 3 2 7

7 4
1 2
3 5
4 3
2 7

输出

复制0 2 2 1 2

0 2 2 1 2

题解:

利用差分的思想

如果op = 1

就是a[x] ++

op = 2

a[x] --

op = 3

            while(x)
            {
                b[x]++;
                x/=2;
            }

把一条链上的点都加1

op = 4

相当于把一条链上的点都减一

a[1]++

    for(int i = 1;i <= n;i++)
    {
        a[i] += a[i/2];
    }

每个点的值要加上层的标记(差分的思想)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
//1 1 3 3 3
int n,k,m;
int a[10000400];
int b[10000400];
int c[10000400];
void solve()
{
	int n,m;
	cin >> n >>m;
	while(m--)
	{
		int op,x;
		cin >>op>>x;
		if(op == 1)
		{
			a[x]++;
		}
		else if(op == 2)
		{
			a[x]--;
			a[1]++;
		}
		else if(op == 3)
		{
			while(x)
			{
				b[x]++;
				x/=2;
			}
		}
		else
		{
			while(x)
			{
				b[x]--;
				x/=2;
			}
			a[1]++;
		}
	}
	for(int i = 1;i <= n;i++)
	{
		a[i] += a[i/2];
	}
	for(int i = 1;i <= n;i++)
	{
		c[a[i] + b[i]]++;
	}
	for(int i = 1;i <= n;i++)
	{
		cout<<c[i]<<"\n";
	}
}
signed main()
{
	int t = 1;
	//cin >> t;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(t--)
	{
		solve();
	}
}
//4 8 12 16 20 24
//
 
//1 2 3 2
//1 2 2 2 2 3
//