题解 | #剖分#

E、剖分

#include<iostream>
using namespace std;
int a[10000009],b[10000009],c[10000009];
//a数组用于差分处理，b数组用于存节点权重，c用于存每个权重的数量
int main()
{
    int n,m;
    cin>>n>>m;
    int t=m;
    while(m--)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            a[x]++;
        }
        else if(op==2)
        {
            if(x!=1)
            {
                a[1]++,a[x]--;
                //a[1]++所有节点权重都加一,a[x]--以x为根节点的子树节点权重为保持不变差分处理减一
            }
        }
        else if(op==3)
        {
            while(x)
            {
                b[x]++;
                x/=2;
                //暴力处理，直接在节点本身加权重
            }
        }
        else{
            while(x)
            {
                b[x]--;
                x/=2;
            }
            a[1]++;//所有节点权重都加一,不该加的部分已在b数组中减了
        }
        
    }
    
    for(int i=1;i<=n;i++)
    {
        a[i]+=a[i/2];
        b[i]+=a[i];//自身权重+差分处理权重=op处理后的权重
        c[b[i]]++;桶记各权重个数
    }
    for(int i=0;i<=t;i++)cout<<c[i]<<" ";
        
}