「HNOI2010」城市建设 - CDQ分治缩小数据规模

题目大意

修改边权动态维护MST。

---

CDQ分治缩小数据规模

本题略难。
有两种解法可以做：CDQ分治+缩小规模、CDQ分治+LCT。
本处不提及第二种解法。

这大概是CDQ分治的第三个应用了吧，缩小数据规模，使得能在允许的时间范围内完成询问。

目前接触到的缩小数据规模的数据结构有两种：CDQ分治、分块。虽然它们都缩小了数据规模，但原理是不一样的。
CDQ分治的原理是在对修改区间分治，在分治使的修改操作变得逐渐具体的过程中筛掉无用的或选出有用的，往下分治的时候就不必继续使用它们。
分块的原理是，将每个块分为$O(\sqrt{n})$的大小，从而允许块内与块间进行更高复杂度的算法。

---

题目分析

CDQ分治修改操作。
若$L==R$修改边权，求一次最小生成树。
在分治的过程中不断执行以下两个操作：

• Constraction操作：缩掉必须使用的边
  将$L\rightarrow R$区间内的边权修改为-inf，求一次最小生成树，在最小生成树上且不是-inf的边必定要选，把必须要选的边缩掉，其余的边加入下一层分治的边集中。
• Reduction操作：删除无用边
  将$L\rightarrow R$区间内的边权修改为inf，求一次最小生成树，不在最小生成树上且不是inf的边以后不会用到，把它们全部删除，剩下的边加入下一层分治的边集中。

时间复杂度并不显然，但是经过这两个操作后点、边的规模可以降到$O(R-L+1)$，最后单位区间的Kruskal便可以视为$O(1)$了，总时间复杂度为$O(n\log^2n)$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=50005;
struct Edge {
	int from,to,pos;
	LL dist;
	bool operator < (const Edge& b) const {
		return dist<b.dist;
	}
};
vector<Edge>E[25],edges;
struct Query {
	int x,y;
} q[maxn];
int father[maxn],M[maxn],a[maxn];
LL Ans[maxn];
int Get_Father(int x) {
	if(father[x]==x)return x;
	return father[x]=Get_Father(father[x]);
}
void Clear(vector<Edge>& edges) {
	for(auto& e:edges) {
		father[e.from]=e.from;
		father[e.to]=e.to;
	}
}
void Constraction(vector<Edge>& edges,LL& ans) { //缩必须边 
	Clear(edges);
	sort(edges.begin(),edges.end());
	static vector<Edge>tmpedges;
	tmpedges.clear();
	for(auto& e:edges) {
		int fx=Get_Father(e.from),fy=Get_Father(e.to);
		if(fx==fy)continue;
		father[fx]=fy;
		tmpedges.push_back(e);
	}
	Clear(tmpedges);
	for(auto& e:tmpedges) {
		int fx=Get_Father(e.from),fy=Get_Father(e.to);
		if(e.dist!=-0x7fffffff/2&&fx!=fy) { //必须边 
			father[fx]=fy;
			ans+=e.dist;
		}
	}
	tmpedges.clear();
	for(auto& e:edges)
		if(Get_Father(e.from)!=Get_Father(e.to)) { //非必须边保留下来
			tmpedges.push_back(e); 
			M[e.pos]=tmpedges.size()-1;
			tmpedges.back().from=father[e.from];
			tmpedges.back().to=father[e.to];
		}
	edges=tmpedges;
}
void Reduction(vector<Edge>& edges) { //删除无用边 
	Clear(edges);
	sort(edges.begin(),edges.end());
	static vector<Edge>tmpedges;
	tmpedges.clear();
	for(auto& e:edges) {
		int fx=Get_Father(e.from),fy=Get_Father(e.to);
		if(fx!=fy) {
			father[fx]=fy;
			tmpedges.push_back(e);
			M[e.pos]=tmpedges.size()-1;
		} else if(e.dist==0x7fffffff/2)tmpedges.push_back(e),M[e.pos]=tmpedges.size()-1;
	}
	edges=tmpedges;
}
void CDQBinary(int Left,int Right,int depth,LL ans) {
	if(Left==Right)a[q[Left].x]=q[Left].y;
	for(auto& e:E[depth])e.dist=a[e.pos];
	edges=E[depth];
	int tmp=0;
	for(auto& e:E[depth])M[e.pos]=tmp++;
	if(Left==Right) {
		Ans[Left]=ans;
		Clear(edges);
		sort(edges.begin(),edges.end());
		for(auto& e:edges) {
			int fx=Get_Father(e.from),fy=Get_Father(e.to);
			if(fx==fy)continue;
			father[fx]=fy;
			Ans[Left]+=e.dist;
		}
		return;
	}
	for(int i=Left; i<=Right; i++)edges[M[q[i].x]].dist=-0x7fffffff/2;
	Constraction(edges,ans);
	for(int i=Left; i<=Right; i++)edges[M[q[i].x]].dist=0x7fffffff/2;
	Reduction(edges);
	E[depth+1]=edges;
	int mid=(Left+Right)>>1;
	CDQBinary(Left,mid,depth+1,ans);
	CDQBinary(mid+1,Right,depth+1,ans);
}
int n,m,Q;
int main() {
	n=Get_Int();
	m=Get_Int();
	Q=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		E[0].push_back((Edge) {
			x,y,i,v
		});
		a[i]=v;
	} 
	for(int i=1; i<=Q; i++) {
		q[i].x=Get_Int();
		q[i].y=Get_Int();
	}
	CDQBinary(1,Q,0,0);
	for(int i=1; i<=Q; i++)printf("%lld\n",Ans[i]);
	return 0;
}