C++(g++ 7.5.0) 解法, 执行用时: 592ms, 内存消耗: 158076K, 提交时间: 2022-11-25 21:13:50

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7+10;
int w[N],a[N],b[N],n;
void dfs1(int u,int t){
    if(u<1)return;
    if(t)a[u]++;
    else a[u]--;
    dfs1(u/2,t);
}
signed main()
{
	int m,op,x,ans=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>op>>x;
        if(op==1)b[x]++;
        else if(op==2)b[x]--,ans++;
        else if(op==3)dfs1(x,1);
        else dfs1(x,0),ans++;
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i/2];
    }
    for(int i=1;i<=n;i++){
        w[a[i]+ans+b[i]]++;
    }
    for(int i=0;i<=m;i++)
        cout<<w[i]<<" ";
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1160ms, 内存消耗: 104520K, 提交时间: 2022-11-27 17:07:56

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
typedef long long LL;
int d[N],f[N],v[N];
int n,m;
void dfs(int u,int fa)
{
	if(u>n)return ;
	d[u]+=d[fa];
	dfs(2*u,u);
	dfs(2*u+1,u);
	f[u]=f[u]+f[2*u]+f[2*u+1];
}
int main()
{
	
	cin>>n>>m;
	int g=0;
	for(int i=0;i<m;i++)
	{
		int op,x;
		cin>>op>>x;
		if(op==1)d[x]++;
		else if(op==2)d[x]--,g++;
		else if(op==3)f[x]++;
		else f[x]--,g++;
	}
	dfs(1,0);
	map<int,int>v;
	for(int i=1;i<=n;i++)v[g+d[i]+f[i]]++;
	for(int i=0;i<=m;i++)cout<<v[i]<<' ';
	
}