CDQ套数据结构——城市建设做法一

发表于

BZOJ2001 HNOI2010城市建设 传送门

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

14
10
9

Solution

LCT，用分治给每个时间点分配边。

相当于利用分治，把原本变化的边不断拆解，分配下去，最后每个子节点就是那个时刻该有的数据

代码。。。bzoj上根本卡不过（LCT指针版没什么用。。)

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
203
204
205
206
207
208
209
210
#include<stdio.h>
#include<ctype.h>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const int N=200005;
inline int _R(){
	int d=0;char t=getchar();
	while(!isdigit(t))t=getchar();
	for(;isdigit(t);t=getchar())d=(d<<3)+(d<<1)+t-'0';
	return d;
}
struct Node{
	Node *Son[2],*Max,*Fa;
	int x,y,val,id;
	bool rev;
}pool[N],*null,*it[N];

namespace LCT{

	void Init(int sz){
		it[0]=null=pool;
		null->Son[0]=null->Son[1]=null->Fa=null->Max=null;
		null->x=null->y=null->val=null->rev=0;
		for(int i=1;i<=sz;i++){
			it[i]=pool+i;
			it[i]->Son[0]=it[i]->Son[1]=it[i]->Fa=it[i]->Max=null;
		}
	}
	inline bool IsRoot(Node* x){
		return x->Fa==null||(x->Fa->Son[0]!=x&&x->Fa->Son[1]!=x);
		//return !Fa[x]||(Son[Fa[x]][0]!=x&&Son[Fa[x]][1]!=x);
	}
	inline void Setr(Node* x){
		x->rev^=1;
		swap(x->Son[0],x->Son[1]);
		//Rev[x]^=1;
		//swap(Son[x][0],Son[x][1]);
	}
	inline void PushUp(Node* x){
		x->Max=x;
		if(x->Son[0]->Max->val>x->Max->val)x->Max=x->Son[0]->Max;
		if(x->Son[1]->Max->val>x->Max->val)x->Max=x->Son[1]->Max;
		//if(Val[Max[l]]>Val[Max[x]])Max[x]=Max[l];
		//if(Val[Max[r]]>Val[Max[x]])Max[x]=Max[r];
	}
	inline void PushDown(Node* x){
		if(x->rev){
			x->rev=0;
			if(x->Son[0]!=null)Setr(x->Son[0]);
			if(x->Son[1]!=null)Setr(x->Son[1]);
		}
		//if(Rev[x]){
		//	Rev[x]=0;
		//	if(Son[x][0])Setr(Son[x][0]);
		//	if(Son[x][1])Setr(Son[x][1]);
		//}
	}
	inline void Rotate(Node* x){
		Node *y=x->Fa,*z=y->Fa;
		int l=y->Son[0]==x,r=l^1;
		if(!IsRoot(y))z->Son[z->Son[1]==y]=x;x->Fa=z;
		y->Son[r]=x->Son[l],x->Son[l]->Fa=y,x->Son[l]=y,y->Fa=x;
		PushUp(y),PushUp(x);
		//int y=Fa[x],z=Fa[y],l=Son[y][0]==x,r=l^1;
		//if(!IsRoot(y))Son[z][Son[z][1]==y]=x;Fa[x]=z;
		//Son[y][r]=Son[x][l],Fa[Son[x][l]]=y,Son[x][l]=y,Fa[y]=x;
		//PushUp(y),PushUp(x);
	}
	Node* s[N];
	int top;
	void Splay(Node* x){
		s[top=1]=x;
		for(Node* i=x;!IsRoot(i);i=i->Fa)s[++top]=i->Fa;
		while(top)PushDown(s[top--]);
		while(!IsRoot(x)){
			Node *y=x->Fa,*z=y->Fa;
			//int y=Fa[x],z=Fa[y];
			if(!IsRoot(y)){
				if(z->Son[0]==y^y->Son[0]==x)Rotate(x);
				else Rotate(y);
			}
			else Rotate(x);
		}
	}
	void Access(Node* x){
		for(Node* t=null;x!=null;t=x,x=x->Fa){
			Splay(x);
			x->Son[1]=t;
			PushUp(x);
		}
	}
	void MakeToRoot(Node* x){
		Access(x);Splay(x);Setr(x);
	}
	bool Bridge(int _x,int _y){
		Node *x=it[_x],*y=it[_y];
		Access(x),Splay(x);
		while(x->Son[0]!=null)x=x->Son[0];
		Access(y),Splay(y);
		while(y->Son[0]!=null)y=y->Son[0];
		return x==y;
	}
	void Link(int _x,int _y){
		Node *x=it[_x],*y=it[_y];
		MakeToRoot(x);
		x->Fa=y;
	}
	void Cut(int _x,int _y){
		Node *x=it[_x],*y=it[_y];
		MakeToRoot(x);
		Access(y),Splay(y);
		y->Son[0]=x->Fa=null;
		PushUp(y);
	}
	Node* GetMax(int _x,int _y){
		Node *x=it[_x],*y=it[_y];
		MakeToRoot(x);
		Access(y),Splay(y);
		return y->Max;
	}
}

int n,m,T,Last[N];
ll Ans[N];
struct Edge{
	int x,y,z,l,r,id;
}E[N];

typedef pair<int,int> pii;
typedef pair<int,pii> piii;
stack<piii>s;
void Recover(int x){
	while(s.size()>x){
		piii tmp=s.top();
		s.pop();
		if(tmp.first==1)LCT::Cut(tmp.second.first,tmp.second.second);	
		else LCT::Link(tmp.second.first,tmp.second.second);
	}
}

void CDQ(int l,int r,ll d,vector<Edge>e){
	using namespace LCT;
	int mid=l+r>>1,now=::s.size();
	vector<Edge>v1,v2;
	for(vector<Edge>::iterator it=e.begin();it!=e.end();it++){
		if(it->l==l&&it->r==r){
			if(!Bridge(it->x,it->y)){
				Link(it->x,it->id);
				Link(it->y,it->id);
				d+=it->z;
				::s.push(piii(1,pii(it->x,it->id)));
				::s.push(piii(1,pii(it->y,it->id)));
			}
			else{
				Node* t=GetMax(it->x,it->y);
				if(t->val>it->z){
					Cut(t->id,t->x);
					Cut(t->id,t->y);
					Link(it->id,it->x);
					Link(it->id,it->y);
					d+=it->z-t->val;
					::s.push(piii(2,pii(t->id,t->x)));
					::s.push(piii(2,pii(t->id,t->y)));
					::s.push(piii(1,pii(it->id,it->x)));
					::s.push(piii(1,pii(it->id,it->y)));
				}
			}
		}
		else if(it->r<=mid)v1.push_back(*it);
		else if(it->l>mid)v2.push_back(*it);
		else v1.push_back((Edge){it->x,it->y,it->z,it->l,mid,it->id}),
			 v2.push_back((Edge){it->x,it->y,it->z,mid+1,it->r,it->id});
	}
	if(l==r)Ans[l]=d;
	else CDQ(l,mid,d,v1),CDQ(mid+1,r,d,v2);
	Recover(now);
}
vector<Edge>v;
int main(){
	int i,j,k,x,y,z;
	n=_R(),m=_R(),T=_R();
	for(i=1;i<=m;i++){
		E[i].x=_R(),E[i].y=_R(),E[i].z=_R();
		Last[i]=i;
		E[i].l=1,E[i].r=T;
	}
	for(i=1;i<=T;i++){
		x=_R(),y=_R();
		E[Last[x]].r=i-1;
		E[i+m]=E[Last[x]];
		Last[x]=i+m;
		E[i+m].l=i,E[i+m].r=T,E[i+m].z=y;
	}
	LCT::Init(n+m+T);
	for(i=1;i<=m+T;i++)
		if(E[i].l<=E[i].r){
			E[i].id=n+v.size()+1;
			x=E[i].id;
			pool[x].id=E[i].id;
			pool[x].x=E[i].x;
			pool[x].y=E[i].y;
			pool[x].val=E[i].z;
			v.push_back(E[i]);
		}
	CDQ(1,T,0,v);
	for(i=1;i<=T;i++)printf("%lld\n",Ans[i]);
}