45分求助
查看原帖
45分求助
651908
8NewOC楼主2023/7/6 11:08
#include<bits/stdc++.h>
#define ll long long
#define INF int
using namespace std;
ll sum[200001],ans,num[2000001];
INF n,m,f[200001];
ll find(ll x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void change(ll x,ll k){
	for(ll i=x;i<=n;i+=i&(-i))sum[i]+=k;
}
ll w(ll x){
	ll cnt=0;
	for(ll i=x;i>0;i-=i&(-i))cnt+=sum[i];
	return cnt;
}
INF main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	if(n<=5e4){
		for(ll i=1;i<=n;++i) f[i]=i;
		for(ll j=1;j<=m;++j){
			ll q,x,y,z;
			cin>>q;
			if(q==1) cin>>x>>y,f[find(x)]=find(y);
			if(q==2){
				cin>>x>>y>>z;
				for(ll i=x;i<=y;++i)sum[i]+=z;
			}
			if(q==3){
				ans=0,cin>>x;
				for(ll i=1;i<=n;++i)if(find(x)==find(i))ans+=sum[i];
				cout<<ans<<endl;
			}
		}
	}
	else if(n>=1e5){
		for(ll i=1;i<=m;++i){
			ll q,x,y,z;
			cin>>q;
			if(q==1) cin>>x>>y;
			if(q==2){
				cin>>x>>y>>z;
				change(x,z);
				change(y+1,-z);
			}
			if(q==3){
				cin>>x;
				cout<<w(x)<<endl;
			}
		}
	}
	else{
		for(ll i=1;i<=n;++i) f[i]=i;
		for(ll j=1;j<=m;++j){
			ll q,x,y,z;
			cin>>q;
			if(q==1){
				int x,y;
				cin>>x>>y;
				num[find(x)]+=num[find(y)];
				f[find(y)]=find(x);
			}
			if(q==2){
				int x,y,z;
				cin>>x>>y>>z;
				for(int i=x;i<=y;i++){
					num[find(i)]+=z;
				}
			}
			if(q==3){
				long long x;
				cin>>x;
				cout<<num[find(x)]<<endl;
			}
		}
	}		
}
2023/7/6 11:08
加载中...