MnZn刚学操作分块求调
查看原帖
MnZn刚学操作分块求调
999274
CNS_5t0_0r2楼主2025/1/2 13:44
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 9,M = 1e5 + 9,Q = 1e5 + 9,SqrtQ = 359;
int n,m,q;
int ans[Q];
struct DSU{
	int fa[N];
	int siz[N];
	stack<int> s;
	void init(){
		for(int i = 1;i <= n;i++){
			fa[i] = i;
			siz[i] = 1;
		}
	}
	int father(int x){
		return fa[x] == x ? x : fa[x] = father(fa[x]);
	}
	void merge(int x,int y,int typ){
		x = father(x);y = father(y);
		if(x == y)
			return;
		if(siz[x] < siz[y])
			swap(x,y);
		fa[y] = x;
		siz[x] += y;
		if(typ == 1)//本次合并将来要撤销 
			s.push(y);
	}
	void cancel(){
		while(!s.empty()){
			int tp = s.top();
			s.pop();
			siz[fa[tp]] -= siz[tp];
			fa[tp] = tp;
		}
	}
} dsu;
struct edge{
	int u,v,w;
} e[M],tmp1[M],tmp2[M];
bool cmp1(edge e1,edge e2){
	return e1.w > e2.w;
}
struct option{
	int id,x,y;
} modify[SqrtQ],query[SqrtQ];
bool cmp2(option op1,option op2){
	return op1.y > op2.y;
}
int top1,top2;
void solve(){
	for(int i = 1;i <= m;i++)
		tmp2[i] = tmp1[i] = e[i];
	for(int i = 1;i <= top2;i++)
		tmp1[modify[i].x].w = -1;
	sort(tmp1 + 1,tmp1 + m + 1,cmp1);
	sort(query + 1,query + top2 + 1,cmp2);
	int i = 1,j = 1;
	while(i <= top2){
		while(j <= m && tmp1[j].w >= query[i].y){
			dsu.merge(tmp1[j].u,tmp1[j].v,0);
			j++;
		}
		for(int k = 1;k <= top1 && modify[k].id < query[i].id;k++)
			tmp2[modify[k].x].w = modify[k].y;
		for(int k = 1;k <= top1;k++)
			if(tmp2[modify[k].x].w >= query[i].y)
				dsu.merge(tmp2[modify[k].x].u,tmp2[modify[k].x].v,1);
		ans[query[i].id] = dsu.siz[dsu.father(query[i].x)];
		dsu.cancel();
		i++;
	}
	for(int i = 1;i <= top1;i++)
		e[modify[i].x].w = modify[i].y;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	dsu.init();
	for(int i = 1;i <= m;i++)
		cin >> e[i].u >> e[i].v >> e[i].w;
	cin >> q;
	int block_len = (int)sqrt(q),block_cnt = (q + block_len - 1) / block_len;
	for(int i = 1;i <= block_cnt;i++){
		top1 = top2 = 0;
		for(int j = (i - 1) * block_len + 1;j <= min(i * block_len,n);j++){
			int op,x,y;
			cin >> op >> x >> y;
			if(op == 1)
				modify[++top1] = (option){i,x,y};
			else if(op == 2)
				query[++top2] = (option){i,x,y};
		}
		solve();
	}
	for(int i = 1;i <= n;i++)
		cout << ans[i] << '\n';
	return 0;
}
2025/1/2 13:44
加载中...