NKOJ 2936 （BZOJ 2001）城市建设（CDQ分治+LCT）

发表于 |
字数统计: 1,851字 | 阅读时长 ≈ 10min

P2936【FJ Training 2014 Day2】城市建设

问题描述

PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和，Louis决定求助于你来完成这个任务。
因版权问题，题目已隐藏。如有需要请私下联系root或nodgd。

输入格式

第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。
接下来有M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1<=Xi,Yi<=N, 0<=Zi<=5*107)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zi修改为d)。

输出格式

包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。

样例输入

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

样例输出

14
10
9

提示

对于20%的数据, n≤1000，m≤6000，Q≤6000。
另有20%的数据，n≤1000，m≤50000，Q≤8000，修改后的代价不会比之前的代价低。
对于100%的数据, n≤20000，m≤50000，Q≤50000。

题目让维护一个边权不断变化的动态最小生成树。容易发现修改边权相当于删除一条边再添加一条边。
容易发现LCT可以轻松维护加边操作，但无法维护删边操作。
此时考虑用CDQ分治去掉删边操作。
预处理每条边存在的时间，按时间分治，每次将覆盖了整个左区间或右区间的边插入到左区间或右区间的LCT中。分治底层就是每一个时刻的答案LCT。
但是并不能开$n\log n$个LCT，空间承受不了，容易发现LCT上的操作是可以撤销的，LINK和CUT互为逆操作，因此只需要用栈记录一下操作，回溯的时候撤销就行。这样就只需要开一颗全局LCT。

最终时间复杂度$O(2m\log q\log(2n))$，加上LCT的大常数，导致这样做非常地卡常，想要通过此题需要优秀的常数。

另外本题有另一个利用MST性质的做法，大致是利用MST将边分成三类同时缩点，不断缩小边集和点集。时间复杂度一样，但常数小。

代码（常数巨大以至于不能AC）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 800005
#define ll long long
using namespace std;
struct node{int x,y,z,id;}E[N],LE[N],RE[N];
int n,m,q,L[N],R[N],TOT,tot,Hash[N],la[N];
int ls[N],rs[N],fa[N],Max[N],id[N],v[N],rev[N],S[N],top;
ll ans,Ans[N],Atop;
node AS[N];
inline char getc()
{
    static char *SS,*TT,buf[N]; 
    if(SS==TT)
    {
        TT=(SS=buf)+fread(buf,1,N,stdin);
        if(SS==TT)return EOF;
    }
    return *SS++;
}
inline bool isdigit(char x)
{return '0'<=x&&x<='9';}
inline int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());)D=D*10+ch-'0';
    return D;
}  
int GM(int x,int y,int z)
{
	if(x>=y&&x>=z)return x;
	if(y>=z)return y;
	return z;
}
bool Isroot(int x)
{return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
void MT(int p)
{
	Max[p]=GM(v[p],Max[ls[p]],Max[rs[p]]);
	if(Max[p]==v[p])id[p]=p;
	else if(Max[p]==Max[ls[p]])id[p]=id[ls[p]];
	else id[p]=id[rs[p]];
}
void PD(int p)
{
	if(rev[p])
	{
		swap(ls[p],rs[p]);
		rev[ls[p]]^=1;
		rev[rs[p]]^=1;
		rev[p]^=1;
	}
}
void Zig(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	ls[y]=rs[x];fa[rs[x]]=y;
	rs[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Zag(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	rs[y]=ls[x];fa[ls[x]]=y;
	ls[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Splay(int x)
{
	int i,y,z;
	S[++top]=x;
	for(i=x;!Isroot(i);i=fa[i])S[++top]=fa[i];
	while(top)PD(S[top--]);
	while(!Isroot(x))
	{
		y=fa[x];z=fa[y];
		if(!Isroot(y))
		{
			if(y==ls[z])x==ls[y]?(Zig(y),Zig(x)):(Zag(x),Zig(x));
			else x==rs[y]?(Zag(y),Zag(x)):(Zig(x),Zag(x));
		}
		else x==ls[y]?Zig(x):Zag(x);
	}
}
void Access(int x)
{
	for(int t=0;x;x=fa[x])
	{
		Splay(x);
		rs[x]=t;
		MT(x);t=x;
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	rev[x]^=1;
}
int Findroot(int x)
{
	Access(x);
	Splay(x);
	while(ls[x])x=ls[x];
	return x;
}
void Link(int x,int y)
{
	Makeroot(x);
	fa[x]=y;
}
void Cut(int x,int y)
{
	Makeroot(x);
	Access(y);
	Splay(y);
	ls[y]=fa[x]=0;
}
void Insert(node &p,int ty)
{
	int x=p.x,y=p.y,t,d;
	if(Findroot(x)!=Findroot(y))
	{
		Link(x,p.id);
		Link(y,p.id);
		if(ty)AS[++Atop]=(node){x,p.id,1,0},AS[++Atop]=(node){y,p.id,1,0};
		ans+=p.z;
	}
	else
	{
		Makeroot(x);
		Access(y);
		Splay(y);
		if(Max[y]>p.z)
		{
			t=id[y];
			d=Hash[t];
			Cut(t,E[d].x);
			Cut(t,E[d].y);
			ans-=v[t];
			if(ty)AS[++Atop]=(node){t,E[d].x,2,0},AS[++Atop]=(node){t,E[d].y,2,0};
			Link(x,p.id);
			Link(y,p.id);
			ans+=p.z;
			if(ty)AS[++Atop]=(node){x,p.id,1,0},AS[++Atop]=(node){y,p.id,1,0};
		}
	}
}
void Recover(int T)
{
	while(Atop!=T)
	{
		if(AS[Atop].z==1)Cut(AS[Atop].x,AS[Atop].y);
		else Link(AS[Atop].x,AS[Atop].y);
		Atop--;
	}
}
void CDQ(int l,int r)
{
	int i,j,k,x,y,las=Atop;
	ll pans=ans;
	if(l==r){Ans[l]=ans;return;}
	int mid=l+r>>1;
	for(i=mid+1;i<=r;i++)if(L[i]<=l)Insert(LE[i],1);
	CDQ(l,mid);Recover(las);ans=pans;
	for(i=l;i<=mid+1;i++)if(R[i]>r)Insert(RE[i],1);
	CDQ(mid+1,r);Recover(las);ans=pans;
}
int main()
{
	int i,j,k,x,y,z;
	n=read();m=read();q=read();tot=n;
	for(i=1;i<=m;i++)
	{
		x=read();y=read();z=read();
		E[++TOT]=(node){x,y,z,0};
		la[TOT]=0;
	}
	for(i=1;i<=q;i++)
	{
		x=read();y=read();
		L[i]=la[x];la[x]=i;
		LE[i]=E[x];E[x].z=y;
		R[L[i]]=i;RE[L[i]]=LE[i];
		LE[i].id=++tot;v[tot]=LE[i].z;Hash[tot]=x;
		RE[L[i]].id=++tot;v[tot]=LE[i].z;Hash[tot]=x;
	}
	for(i=1;i<=TOT;i++)
	{
		k=la[i];
		if(k==0||k==1)E[i].id=++tot,v[tot]=E[i].z,Hash[tot]=i,Insert(E[i],0);
		else R[k]=q+1,RE[k]=E[i],RE[k].id=++tot,v[tot]=RE[k].z,Hash[tot]=i;
	}
	CDQ(1,q);
	for(i=1;i<=q;i++)printf("%lld\n",Ans[i]);
}