问题描述：
PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。
Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。
Louis希望建造最少的道路使得国内所有的城市连通。
但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和，Louis决定求助于你来完成这个任务。
输入格式：
第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。
接下来有M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1<=Xi,Yi<=N, 0<=Zi<=5*10^7)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。
接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zi修改为d)。
输出格式：
包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。
数据范围：
对于20%的数据, n≤1000，m≤6000，Q≤6000。
另有20%的数据，n≤1000，m≤50000，Q≤8000，修改后的代价不会比之前的代价低。
对于100%的数据, n≤20000，m≤50000，Q≤50000。
一道奇奇怪怪的题，为什么会是CDQ啊（刷新认知）。但，既然ta是那ta就是吧。
读完题，应该知道有最小生成树，所以现在我们知道 ta 是 MST + CDQ 。
但ta的图是会变的，如果每次都跑一次 Kruskal 肯定是不行的，那怎么优化呢？
因为 CDQ 所以一定是离线的，对于一个修改区间 [ L , R ] ，可以把边分为三类：
① 一定有用的边，即一定在 MST 上的边；
② 一定没有用的边，即一定不在 MST 上的边；
③ 不一定有用的边，即不一定在 MST 上的边。
对于①而言，可以把相连的点缩为一个点；对于②而言，可以把无用边删去。这样缩点、删边后图的规模会越来越小。
之后再处理 [ L , M ] 和 [ M + 1 , R ] 区间（M = ( L + R ) >> 1）。
怎么实现呢？
对于一个修改区间 [ L , R ] 的边全部设为 -inf ，求一次MST，MST上的点是一定有用的边；对于一个修改区间 [ L , R ] 的边全部设为 inf ，求一次MST，MST上的点是一定没用的边。
这两点真的很好证明，读者自证不难。
还是YY一哈，当区间 [ L , R ] 的边全部为 -inf 时，跑MST的时候，他们一定是优先选择的，如果还有其他边被选，那么这些边一定是会出现在接下来的MST中的；Vice Versa。
值得注意的是：CDQ过程中，只是用来减少边数的，真正的修改边权，是在 L == R 时进行的。
当然，并查集是必不可少的，要维护连通性嘛，但因为要存的数据太大了，并查集需要实现 可撤销 。具体而言，由于树深是不会超过20的，可以开20个来分别存储，即分层。
更多细节可参考代码。
Code:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
int n,m,q,Fa[50005],A[50005],B[50005],C[50005],Deep[21];
long long Ans[50005];
struct node {int x,y,z,Id;}E[21][50005],Tmp[50005],Temp[50005];
bool cmp(node a,node b) {return a.z<b.z;}
struct nodden {int k,d;}Q[50005];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
char ch;int x(0);
while((ch=gc)<48);
do x=x*10+ch-48;while((ch=gc)>=48);
return x;
}
inline int GetFa(int x) {return (Fa[x]==x)?x:Fa[x]=GetFa(Fa[x]);}
inline void Link(int x,int y)
{
x=GetFa(x),y=GetFa(y);if(x==y) return;
if(B[x]!=B[y]) (B[x]>B[y])?Fa[y]=x:Fa[x]=y;
else Fa[x]=y,++B[y];
}
inline void Find1(int &x,long long &V)
{
int head(0);
for(register int i=1;i<=x;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
sort(Tmp+1,Tmp+x+1,cmp);
for(register int i=1;i<=x;++i)
if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Temp[++head]=Tmp[i];
for(register int i=1;i<=head;++i) Fa[Temp[i].x]=Temp[i].x,Fa[Temp[i].y]=Temp[i].y,B[Temp[i].x]=B[Temp[i].y]=1;
for(register int i=1;i<=head;++i)
if(Temp[i].z!=-inf&&GetFa(Temp[i].x)!=GetFa(Temp[i].y)) Link(Temp[i].x,Temp[i].y),V+=Temp[i].z;
head=0;
for(register int i=1;i<=x;++i)
if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Temp[++head]=node{GetFa(Tmp[i].x),GetFa(Tmp[i].y),Tmp[i].z,Tmp[i].Id};
for(register int i=1;i<=head;++i) C[Tmp[i].Id]=i,Tmp[i]=Temp[i];
x=head;
}
inline void Find2(int &x)
{
int head(0);
for(register int i=1;i<=x;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
sort(Tmp+1,Tmp+x+1,cmp);
for(register int i=1;i<=x;++i)
if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Temp[++head]=Tmp[i];
else if(Tmp[i].z==inf) Temp[++head]=Tmp[i];
for(register int i=1;i<=head;++i) C[Tmp[i].Id]=i,Tmp[i]=Temp[i];
x=head;
}
inline void CDQ(int L,int R,int deep,long long V)
{
int k=Deep[deep],M=(L+R)>>1;
if(L==R) A[Q[L].k]=Q[L].d;
for(register int i=1;i<=k;++i) E[deep][i].z=A[E[deep][i].Id],Tmp[i]=E[deep][i],C[Tmp[i].Id]=i;
if(L==R)
{
for(register int i=1;i<=k;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
Ans[L]=V,sort(Tmp+1,Tmp+k+1,cmp);
for(register int i=1;i<=k;++i)
if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Ans[L]+=Tmp[i].z;
return;
}
for(register int i=L;i<=R;++i) Tmp[C[Q[i].k]].z=-inf;
Find1(k,V);
for(register int i=L;i<=R;++i) Tmp[C[Q[i].k]].z=inf;
Find2(k);
for(register int i=1;i<=k;++i) E[deep+1][i]=Tmp[i];
Deep[deep+1]=k,CDQ(L,M,deep+1,V),CDQ(M+1,R,deep+1,V);
}
int main()
{
n=read(),m=read(),q=read();
for(register int i=1;i<=m;++i) E[0][i].x=read(),E[0][i].y=read(),E[0][i].z=A[i]=read(),E[0][i].Id=i;
for(register int i=1;i<=q;++i) Q[i].k=read(),Q[i].d=read();
Deep[0]=m,CDQ(1,q,0,0);
for(register int i=1;i<=q;++i) printf("%lld\n",Ans[i]);
return 0;
}
城市建设
