35ps 分块求条

#include<bits/stdc++.h>
#define int long long 
#define Maxn 1000005 
using namespace std;
int id[Maxn];
int lazy[Maxn];
vector<pair<int,int> > s[Maxn];
int A[Maxn];
vector<int> S[Maxn];
signed main()
{
	int n,m;
	cin>>n>>m;
	int M = 475;
	for(int i=1;i<=n;i++) {
		id[i] = i;
		s[i].push_back({(i-1)/M+1,1});
		S[i].push_back(i);
	}
	while(m --) {
		int op; 
		cin>>op;
		if(op == 1) {
			int x,y;
			cin>>x>>y;
			x = id[x],y = id[y];
			if((int)S[x].size() < (int)S[y].size())swap(x,y);
			int j = 0;
			for(int i=0;i<(int)s[x].size();i++) {
				while(j < (int)s[y].size()&&s[y][j].first < s[x][i].first)s[x].push_back(s[y][j]),j ++;
				if(j < (int)s[y].size()&&s[y][j] == s[x][i])s[x][i].second += s[y][j].second,j ++;
			} while(j < (int)s[y].size())s[x].push_back(s[y][j]),j ++;
			if(!s[x].empty())sort(s[x].begin(),s[x].end()); s[y].clear();
			for(int u:S[y])S[x].push_back(u),id[u] = x;
			S[y].clear(); A[x] += A[y];
		} else if(op == 2) {
			int l,r,a;
			cin>>l>>r>>a;
			int lc = (l-1)/M+1,rc = (r-1)/M+1;
			if(lc == rc)for(int i=l;i<=r;i++)A[id[i]] += a;
			else {
				for(int i=l;i<=lc*M;i++)A[id[i]] += a;
				for(int i=(rc-1)*M+1;i<=r;i++)A[id[i]] += a; 
				for(int i=lc+1;i<rc;i++)lazy[i] += a;
			}
		} else {
			int x,ans = 0; 
			cin>>x; x = id[x];
			for(auto u:s[x])ans += u.second*lazy[u.first];
			cout<<ans + A[x]<<"\n";
		}
	}
	return 0;
}