题解 P3206 【[HNOI2010]CITY 城市建设】
shadowice1984 · · 题解
嗯~ o(*￣▽￣*)o，做完这到题想必会对CDQ分治有一个全新的理解吧
其实CDQ分治的本质是：
最大化各个询问间的重复操作从而将复杂度的增加控制在一个log内
而利用的原理就是分治原理:
只要保证任意两个操作和询问间的相对时序不变我们就可以任意处理这个操作-询问序列
那么对于这道题题目是十分粗暴的动态MST
考虑对时间进行分治，也就是说，我们要寻找两个操作序列间的公共部分
为此我们把这张图划分为两个部分，动态边和静态边
如果你CDQ正在考虑(l,r)这一段操作序列
那么L,r内操作涉及的边就称为动态边，这张图其余的边被称为静态边
对于一个动态边，显然是无法处理（因为CDQ就是动态转静态的工具）
所以先放着不动，那么我们考虑简化静态边集合
肯定会有一些静态边是一定会被其他静态边PK掉的，这些边完全没有下传的必要
动态边可能无法联通整张图，那么肯定会有一些静态边充当沟通这些动态边的“桥梁”
这些静态边早晚要被加到MST里的，不如现在就加上
*请务必仔细阅读以上两句话*
那么就可以将不会出现的边从静态边集中删去，将一定会出现的边在静态边集中缩点
从而简化了静态边集
然后这里有一个证明，每次如此操作之后剩余的静态边和动态边大致相等，略
下面考虑如何将（l,r）这段区间拆分为(l,mid)(mid,r)这两个区间
那么我们发现，会有一些动态边变为静态边
这才是这个划分的玄妙之处，动态边会不断的变成静态边，最后变成了一个纯静态的kruskal
显然如果向(l,mid)走的话，只在(mid,r)而不在(l,mid)的动态边会变成静态边
同理如果向(mid,r)走的话，只在(l,mid)而不在(mid,r)的动态边会变成静态边
那么直接在静态边集中插入跑个缩边就行了对吧
终止状态
如果插入的是最后一条动态边，更改这个动态边所对应的权值，并且更新这个动态边对应的查询的答案
为什么要更改呢，因为动转静的过程，边的权值是当前时刻的权值
而如果插入的动态边是最后一条了，证明这个动态边从此以后在也不会被用到
所以就要把它对应的修改做了（不明白自己画一个分治树）
剩下的就是代码实现
这里有两点要讲
1.每一层CDQ开两个vector一个存静态边一个存动态边
2.要删的边可以通过对静态边集跑一个kruskal找出来
3.要缩的边可以通过先把动态边union起来，再跑一个kruskal找出来
4.可以用并查集维护缩点关系
突然发现一个问题，我们的kruskal需要并查集，我们缩点的维护需要并查集
哪里有那么多的内存！
然而那是一次性的路径压缩式并查集，我们的按秩合并并查集，是资瓷撤销的
//应该知道可撤销不是可持久化吧。。。
只要维护一个栈存储操作就可以了，而且资瓷倒流到一个确定的时间点，这样的话我们只需开两个并查集就行了
上代码~（102行，较短）
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
int n;int m;int ask;
struct bcj
{
int fa[20010];int size[20010];
struct opt{int u;int v;};stack <opt> st;
inline void ih(){for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;}
inline int f(int x){return (fa[x]==x)?x:f(fa[x]);}
inline void u(int x,int y)//带撤回
{
int u=f(x);int v=f(y);if(u==v)return;if(size[u]<size[v])swap(u,v);
size[u]+=size[v];fa[v]=u;opt o;o.u=u;o.v=v;st.push(o);
}
inline void undo(){opt o=st.top();st.pop();fa[o.v]=o.v;size[o.u]-=size[o.v];}
inline void clear(int tim){while(st.size()>tim){undo();}}
}s,s1;
struct edge//静态边
{
int u;int v;ll val;int mrk;
friend bool operator <(edge a,edge b){return a.val<b.val;}
}e[50010];
struct moved{int u;int v;};//动态边
struct query{int num;ll val;ll ans;}q[50010];bool book[50010];//询问
vector <edge> ve[30];vector <moved> vq;vector <edge> tr;ll res[30];int tim[30];
inline void pushdown(int dep)//缩边
{
tr.clear();//这里要复制一份，以免无法回撤操作
for(int i=0;i<ve[dep].size();i++){tr.push_back(ve[dep][i]);}
sort(tr.begin(),tr.end());
for(int i=0;i<tr.size();i++)//无用边
{
if(s1.f(tr[i].u)==s1.f(tr[i].v)){tr[i].mrk=-1;continue;}s1.u(tr[i].u,tr[i].v);
}s1.clear(0);res[dep+1]=res[dep];
for(int i=0;i<vq.size();i++){s1.u(vq[i].u,vq[i].v);}vq.clear();
for(int i=0;i<tr.size();i++)//必须边
{
if(tr[i].mrk==-1||s1.f(tr[i].u)==s1.f(tr[i].v))continue;tr[i].mrk=1;
s1.u(tr[i].u,tr[i].v);s.u(tr[i].u,tr[i].v);res[dep+1]+=tr[i].val;
}s1.clear(0);ve[dep+1].clear();
for(int i=0;i<tr.size();i++)//缩边
{
if(tr[i].mrk!=0)continue;
edge p;p.u=s.f(tr[i].u);p.v=s.f(tr[i].v);if(p.u==p.v)continue;
p.val=tr[i].val;p.mrk=0;ve[dep+1].push_back(p);
}return;
}
inline void solve(int l,int r,int dep)
{
tim[dep]=s.st.size();int mid=(l+r)/2;
if(r-l==1)//终止条件
{
edge p;p.u=s.f(e[q[r].num].u);p.v=s.f(e[q[r].num].v);p.val=q[r].val;
e[q[r].num].val=q[r].val;p.mrk=0;ve[dep].push_back(p);pushdown(dep);
q[r].ans=res[dep+1];s.clear(tim[dep-1]);return;
}
for(int i=l+1;i<=mid;i++){book[q[i].num]=true;}
for(int i=mid+1;i<=r;i++)//动转静
{
if(book[q[i].num])continue;
edge p;p.u=s.f(e[q[i].num].u);p.v=s.f(e[q[i].num].v);
p.val=e[q[i].num].val;p.mrk=0;ve[dep].push_back(p);
}
for(int i=l+1;i<=mid;i++)//询问转动态
{
moved p;p.u=s.f(e[q[i].num].u);p.v=s.f(e[q[i].num].v);vq.push_back(p);
}pushdown(dep);//下面的是回撤
for(int i=mid+1;i<=r;i++){if(book[q[i].num])continue;ve[dep].pop_back();}
for(int i=l+1;i<=mid;i++){book[q[i].num]=false;}solve(l,mid,dep+1);
for(int i=0;i<ve[dep].size();i++){ve[dep][i].mrk=0;}
for(int i=mid+1;i<=r;i++){book[q[i].num]=true;}
for(int i=l+1;i<=mid;i++)//动转静
{
if(book[q[i].num])continue;
edge p;p.u=s.f(e[q[i].num].u);p.v=s.f(e[q[i].num].v);
p.val=e[q[i].num].val;p.mrk=0;ve[dep].push_back(p);
}
for(int i=mid+1;i<=r;i++)//询问转动
{
book[q[i].num]=false;
moved p;p.u=s.f(e[q[i].num].u);p.v=s.f(e[q[i].num].v);vq.push_back(p);
}pushdown(dep);solve(mid,r,dep+1);
s.clear(tim[dep-1]);return;//时间倒流至上一层
}
int main()
{
scanf("%d%d%d",&n,&m,&ask);s.ih();s1.ih();
for(int i=1;i<=m;i++){scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].val);}
for(int i=1;i<=ask;i++){scanf("%d%lld",&q[i].num,&q[i].val);}
for(int i=1;i<=ask;i++)//初始动态边
{
book[q[i].num]=true;moved p;p.u=e[q[i].num].u;
p.v=e[q[i].num].v;vq.push_back(p);
}
for(int i=1;i<=m;i++){if(book[i])continue;ve[1].push_back(e[i]);}//初始静态
for(int i=1;i<=ask;i++){book[q[i].num]=false;}solve(0,ask,1);
for(int i=1;i<=ask;i++){printf("%lld\n",q[i].ans);}return 0;//拜拜程序~
}