IV.II.[HNOI2010]城市建设
实际上这题不算狭义上的CDQ分治（先计算左边，再计算左边对右边的贡献，最后计算右边），更像是线段树分治的变种，但是既然大家都认为这就是CDQ那就算是罢……
考虑分治计算。当我们考虑一个区间 \([l,r]\) 时，我们会将所有边分为两类：区间 \([l,r]\) 内操作涉及到的边，称作动态边；未涉及到的边，称作静态边。显然，对于 \([l,r]\) 的子集来说，静态边只会增加不会减少，因此我们考虑在 \([l,r]\) 处就着手缩减静态边集中不需要的部分。
我们发现，对于 \([l,r]\) 中的动态边来说，就算它们全连上也不一定会使得整张图联通，因而连上所有动态边后剩余的连通块间就必然要使用静态边连接。于是这部分的静态边就可以直接跑个MST来联通这些剩余的连通块。显然，此时MST上连出的边，在子区间里是一定会被保留的，故可以缩点。
于是总结一下此部分的操作：
-
对动态边缩点
-
对静态边求MST
-
撤销上述所有操作直到1执行之前，然后连回2中求出的MST上的边。（明显，此部分要使用可撤销冰茶姬）
于是我们现在便率先压缩了点数，并删除了部分静态边。
在上述操作之后，我们又发现一点可乘之机：有部分静态边是不可能出现在最终的MST上的，因为此时它们已经可以被其它静态边替代掉了。
于是我们要再跑一遍静态边的MST，并丢弃掉所有不在MST上的静态边。
显然，一个区间中动态边数量是区间长度级别的；故第一次压缩点数后所剩余的点数也是区间长度级别的；故第二次压缩边数后所剩余的边数也是区间长度级别的；于是我们发现经历上述操作后，区间动态边、静态边数均是区间长度级别的；于是复杂度为分治的一个 \(\log\) 乘以（MST的一个 \(\log\) 以及可撤销冰茶姬的一个 \(\log\)），为 \(n\log^2n\)。
需要注意的是，在递归到区间长度为 \(1\) 时，就直接把修改操作执行，然后暴力跑个MST就行了。
（还有一种解法是非常trivial的线段树分治套LCT，虽然也是 \(O(n\log^2n)\) 但是有着众所周知的大常数因此跑不过去，虽然如果省选时遇到这道题我肯定就暴力上LCT了，因为CDQ分治的解法太太太恶心了）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,id[50010],val[50010],dsu[20010],sz[20010];
struct dat{int u,v,su,sv;dat(int U,int V,int SU,int SV){u=U,v=V,su=SU,sv=SV;}};
stack<dat>s;
void undo(){dsu[s.top().u]=s.top().u,dsu[s.top().v]=s.top().v,sz[s.top().u]=s.top().su,sz[s.top().v]=s.top().sv,s.pop();}
int find(int x){return dsu[x]==x?x:find(dsu[x]);}
struct EDGE{
int x,y,z;
bool merge(){
int X=find(x),Y=find(y);if(X==Y)return false;
if(sz[X]>sz[Y])swap(X,Y);
s.push(dat(X,Y,sz[X],sz[Y])),dsu[X]=Y,sz[Y]+=sz[X];
return true;
}
}e[50010];
ll res,ans[50010];
vector<int>stl,mov;//still edges and movable edges
bool nst[50010];//if the edge is non-still
bool cmp(int x,int y){return e[x].z<e[y].z;}
void solve(int l,int r){
ll RES=res;vector<int>STL=stl,MOV=mov;int SZ=s.size();//those are the old information
// printf("BEF:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
for(int i=l;i<=r;i++)nst[id[i]]=true;
vector<int>tmp;
for(auto i:mov)if(nst[i])tmp.push_back(i);else stl.push_back(i);//separate those once-movable edges into still-movable edges and newly-still edges
for(int i=l;i<=r;i++)nst[id[i]]=false;
mov=tmp;
// printf("MID:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
// for(int i=1;i<=n;i++)printf("%d ",find(i));puts("");
int S=s.size();
for(auto i:mov)e[i].merge();//merge movable edges, to find those must-add edges
tmp.clear();vector<int>pmt;//pmt holds the must-add edges.
sort(stl.begin(),stl.end(),cmp);for(auto i:stl)if(e[i].merge())res+=e[i].z,pmt.push_back(i);else tmp.push_back(i);
stl=tmp;while(s.size()>S)undo();
for(auto i:pmt)e[i].merge();//now must-add edges have all been merged.
// for(int i=1;i<=n;i++)printf("%d ",find(i));puts("");
tmp.clear(),S=s.size();
for(auto i:stl)if(e[i].merge())tmp.push_back(i);
while(s.size()>S)undo();stl=tmp;//now stl holds the minimum-spaning-forest,of those current-still edges
// printf("AFT:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
if(l==r){
e[id[l]].z=val[l],stl.push_back(id[l]);
sort(stl.begin(),stl.end(),cmp);for(auto i:stl)if(e[i].merge())res+=e[i].z;
ans[l]=res;
}else{int mid=(l+r)>>1;solve(l,mid),solve(mid+1,r);}
while(s.size()>SZ)undo();res=RES,stl=STL,mov=MOV;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)dsu[i]=i,sz[i]=1;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),mov.push_back(i);//initially all edges are considered movable
for(int i=1;i<=q;i++)scanf("%d%d",&id[i],&val[i]);
solve(1,q);
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}