rvalue's blog
文章 标签 分类 个人 About Friends
rvalue's blog

目录

[BZOJ 3514]Codechef MARCH14 GERALD07加强版 (CHEF AND GRAPH QUERIES)

rvalue 收录于 cnblogs 题解
   约 1201 字   预计阅读 3 分钟 
迁移提示
本文迁移自博客园, 原文链接

[BZOJ3514] Codechef MARCH14 GERALD07加强版 (CHEF AND GRAPH QUERIES)

题意

$N$ 个点 $M$ 条边的无向图，$K$ 次询问保留图中编号在 $[l,r]$ 的边的时候图中的联通块个数。

部分数据强制在线.

$1\le N,M,K\le200,000$

题解

有点意思的LCT题.

原题好像不强制在线于是可以回滚莫队+带撤销并查集水过去.

我们考虑暴力: 把 $[l,r]$ 内的所有点依次加入并查集, 每次若成功合并两个联通块则将答案 $-1$.

在这种情况下, 一条边会在什么情况下对答案作出什么贡献? 显然是当两条边连接的两个点在左边的合法边都连过之后依然不联通的情况下会造成答案减少 $1$.

考虑快速计算上面的贡献. 容易发现对于某条边 $e$, 依次将它左侧的边加入图中, 一旦在某个边 $e'$ 加入后 $e$ 两边的点已经被联通, 那么继续加下去一定也是联通的. 又因为查询是将一整段区间的边加入图中, 所以一旦 $e$ 和 $e'$ 都被查询区间包含, 则 $e$ 不会对答案作出贡献. 否则一定会对答案造成贡献.

于是只要我们对于所有 $e$ 都预处理出 $e'$ 的位置, 我们就可以通过查询 $[l,r]$ 内小于 $l$ 的值的个数解决. 这个问题显然主席树/分块均可解决.

至于预处理, 我们可以使用LCT. 过程类似于水管局长. 从左到右依次加边, 如果加入边 $(u,v)$ 时出环了, 那么树上从 $u$ 到 $v$ 的路径上最早加入的边就是我们要求的. Splay上维护一下代表边的点的位置就好了(边权转点权的普通操作, 加点)

以及好像把点断掉的时候并不用存这个点代表的边是什么…把这个点Splay到根然后把左右子树直接断掉就好了…

以及黄学长&wulala的变量名真的是生动形象

参考代码

  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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

#include <bits/stdc++.h>
#define _O0 __attribute__((optimize("O0")))

const int MAXN=200010;

struct LCT{
#define lch chd[0]
#define rch chd[1]
#define kch chd[k]
#define xch chd[k^1]
	struct Node{
		int val;
		bool rev;
		Node* prt;
		Node* min;
		Node* chd[2];
		Node(int val):val(val),rev(false),prt(NULL),min(this),chd{NULL,NULL}{}
		inline bool isRoot(){
			return this->prt==NULL||(this->prt->lch!=this&&this->prt->rch!=this);
		}
		inline _O0 void Flip(){
			if(this!=NULL){
				std::swap(this->lch,this->rch);
				this->rev=!this->rev;
			}
		}
		inline void PushDown(){
			if(this->rev){
				this->lch->Flip();
				this->rch->Flip();
				this->rev=false;
			}
		}
		inline void Maintain(){
			this->min=this;
			if(this->lch&&this->lch->min->val<this->min->val)
				this->min=this->lch->min;
			if(this->rch&&this->rch->min->val<this->min->val)
				this->min=this->rch->min;
		}
	};
	std::vector<Node*> N;
	LCT(int n):N(n+1){
		for(int i=1;i<=n;i++)
			N[i]=new Node(INT_MAX);
	}
	void Rotate(Node* root,int k){
		Node* tmp=root->xch;
		root->PushDown();
		tmp->PushDown();
		tmp->prt=root->prt;
		if(!root->isRoot()){
			if(root->prt->lch==root)
				root->prt->lch=tmp;
			else
				root->prt->rch=tmp;
		}
		root->xch=tmp->kch;
		if(root->xch)
			root->xch->prt=root;
		tmp->kch=root;
		root->prt=tmp;
		root->Maintain();
		tmp->Maintain();
	}

	void Splay(Node* root){
		while(!root->isRoot()){
			int k=root->prt->lch==root;
			if(root->prt->isRoot())
				Rotate(root->prt,k);
			else{
				int d=root->prt->prt->lch==root->prt;
				Rotate(k==d?root->prt->prt:root->prt,k);
				Rotate(root->prt,d);
			}
		}
	}

	void Expose(Node* root){
		Splay(root);
		root->PushDown();
		if(root->rch){
			root->rch=NULL;
			root->Maintain();
		}
	}

	void Access(Node* root){
		Expose(root);
		Splay(root);
		while(root->prt){
			Splay(root->prt);
			root->prt->PushDown();
			root->prt->rch=root;
			root->prt->Maintain();
			Splay(root);
		}
	}

	void Evert(Node* root){
		Access(root);
		root->Flip();
	}

	Node* FindRoot(Node* root){
		Access(root);
		Node* ans=root;
		ans->PushDown();
		while(ans->lch){
			ans->PushDown();
			ans=ans->lch;
		}
		Splay(ans);
		return ans;
	}

	void Link(Node* a,Node* b){
		Evert(b);
		b->prt=a;
	}

	void Cut(Node* a,Node* b){
		Evert(a);
		Access(b);
		b->PushDown();
		b->lch->prt=NULL;
		b->lch=NULL;
		b->Maintain();
	}

	int AddEdge(int a,int b,int val){
		if(a==b)
			return val;
		int ret=0;
		if(FindRoot(N[a])==FindRoot(N[b])){
			Evert(N[a]);
			Access(N[b]);
			Node* min=N[b]->min;
			ret=N[b]->min->val;
			Splay(min);
			min->lch->prt=NULL;
			min->rch->prt=NULL;
		}
		N.push_back(new Node(val));
		Link(*N.rbegin(),N[a]);
		Link(*N.rbegin(),N[b]);
		return ret;
	}
#undef lch
#undef rch
#undef kch
#undef xch
};

struct SegTree{
	struct Node{
		int l;
		int r;
		int sum;
		Node* lch;
		Node* rch;
		Node(int l,int r):l(l),r(r),sum(0),lch(NULL),rch(NULL){
			if(l!=r){
				int mid=(l+r)>>1;
				this->lch=new Node(l,mid);
				this->rch=new Node(mid+1,r);
			}
		}
		Node(Node* ptr){
			*this=*ptr;
		}
		void Insert(int x){
			++this->sum;
			if(l!=r){
				if(x<=this->lch->r)
					(this->lch=new Node(this->lch))->Insert(x);
				else
					(this->rch=new Node(this->rch))->Insert(x);
			}
		}
	};
	std::vector<Node*> N;
	SegTree(int n){
		N.push_back(new Node(0,n));
	}
	void Insert(int x){
		N.push_back(new Node(*N.rbegin()));
		(*N.rbegin())->Insert(x);
	}
	int Query(int l,int r,int x){
		return Query(N[l-1],N[r],x);
	}
	int Query(Node* aux,Node* root,int x){
		if(0<=root->l&&root->r<=x)
			return root->sum-aux->sum;
		else{
			int ans=0;
			if(0<=root->lch->r)
				ans+=Query(aux->lch,root->lch,x);
			if(root->rch->l<=x)
				ans+=Query(aux->rch,root->rch,x);
			return ans;
		}
	}
};

int n,m,q,opt;
int lastans;
int ntr[MAXN];

int main(){
	scanf("%d%d%d%d",&n,&m,&q,&opt);
	LCT* lct=new LCT(n);
	SegTree* T=new SegTree(m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		ntr[i]=lct->AddEdge(a,b,i);
	}
	for(int i=1;i<=m;i++)
		T->Insert(ntr[i]);
	for(int i=0;i<q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		l^=opt*lastans;
		r^=opt*lastans;
		printf("%d\n",lastans=n-T->Query(l,r,l-1));
	}
	return 0;
}

https://pic.rvalue.moe/2021/08/02/4c7363ed6308e.jpg

更新于 2019-02-13
阅读原始文档
 LCT/ETT
返回 | 主页