差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_deltix_round_summer_2021 [2021/09/01 21:31]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_deltix_round_summer_2021 [2021/09/01 23:58] (当前版本)
jxm2001
@@ 行 217: / 行 217: @@
 给定编号为 $0\sim 2^n-1$ 的点。$u$ 与 $v$ 连边当且仅当 $u,v$ 的编号二进制表示仅有一位不同。
+接下来 $m$ 个操作，操作分两种：
+  - 删去区间 $[l,r]$ 的所有点
+  - 询问 $a,b$ 两点是否连通
+数据保证每个点最多被删除一次，且每次询问的两点一定存在。
 ==== 题解 ====
+首先考虑一种暴力做法，给第 $i$ 个点一个权值 $a_i$，表示第 $i$ 个点在第 $a_i$ 次操作后被删除，如果第 $i$ 个点直到最后也没被删除则 $a_i=m+1$。
+定义每个边的权值为与该边相邻的两个点权值的最小值。然后逆序处理操作，根据边权从大到小加边同时处理询问，于是并查集维护连通性即可。
+时间复杂度 $O(\text{Na}\times n2^n)$，其中 $O(\text{Na})$ 为并查集复杂度。
+不难发现 $[t2^k,(t+1)2^k-1]$ 的所有点如果 $a_i$ 值相等，那他们一定被加入后就立刻连通，于是可以当作一个点处理。
+考虑线段树优化建图，把每个删点 $[l,r]$ 分为 $O(n)$ 个二的幂次区间，这样最多只有 $O(nm)$ 个点。
+再考虑连边，可以分治处理，假设当前处理到区间 $[t2^k,(t+1)2^k-1]$，可以将点分为左区间的点和右区间的点，只考虑左右区间之间的连边。
+然后不难发现只有左右区间编号差 $2^{k-1}$ 的点正好连一条边，于是可以双指针处理连边，然后继续递归左右区间连边即可。
+不难发现边数是 $O(n^2m)$，于是总时间复杂度 $O(\text{Na}\times n^2m)$。
+进一步考虑优化，发现 $[t2^k,t2^k+x],[t2^k-1-x,t2^k-1](x\lt 2^k)$ 的所有点也是连通的，于是可以猫树优化建图，点数最多 $O(m)$。
+连边也用分治加双指针处理，不过注意如果存在跨左右区间的点需要同时分配到左右区间递归。
+最终边数是 $O(nm)$，于是总时间复杂度 $O(\text{Na}\times nm)$。
 <hidden 查看代码>
 <code cpp>
+const int MAXL=50,MAXM=5e4+5;
+struct opt{
+	LL a,b;
+	int t;
+	bool operator < (const opt &o)const{
+		return a<o.a;
+	}
+};
+vector<opt> upd,nodes;
+void Insert(opt node,LL vl,LL vr){
+	if(node.a==node.b)
+	nodes.push_back(node);
+	else{
+		LL vm=vl+vr>>1;
+		if(node.a<=vm&&node.b>vm){
+			nodes.push_back(opt{node.a,vm,node.t});
+			nodes.push_back(opt{vm+1,node.b,node.t});
+		}
+		else if(node.b<=vm)
+		Insert(node,vl,vm);
+		else
+		Insert(node,vm+1,vr);
+	}
+}
+vector<pair<int,int> > edges[MAXM];
+void build(int ql,int qr,LL vl,LL vr){
+	if(ql==qr)
+	return;
+	LL vm=vl+vr>>1,len=vm-vl+1;
+	int qm1=ql,qm2;
+	while(qm1<qr&&nodes[qm1+1].a<=vm)qm1++;
+	qm2=qm1+(nodes[qm1].b>vm?0:1);
+	int pos1=ql,pos2=qm2;
+	while(pos1<=qm1&&pos2<=qr){
+		edges[min(nodes[pos1].t,nodes[pos2].t)].emplace_back(pos1,pos2);
+		if(nodes[pos1].b+len<nodes[pos2].b)
+		pos1++;
+		else if(nodes[pos1].b+len>nodes[pos2].b)
+		pos2++;
+		else
+		pos1++,pos2++;
+	}
+	build(ql,qm1,vl,vm);
+	build(qm2,qr,vm+1,vr);
+}
+int p[MAXM<<2];
+int Find(int x){
+	return p[x]==x?x:p[x]=Find(p[x]);
+}
+pair<LL,LL> query[MAXM];
+vector<LL> mp;
+char buf[MAXL];
+int main(){
+	int n=read_int(),m=read_int();
+	LL maxv=(1LL<<n)-1;
+	_for(i,0,m){
+		scanf("%s",buf);
+		LL l=read_LL(),r=read_LL();
+		if(buf[0]=='b'){
+			upd.push_back(opt{l,r,i});
+			query[i]=make_pair(-1LL,-1LL);
+		}
+		else
+		query[i]=make_pair(l,r);
+	}
+	query[m]=make_pair(-1LL,-1LL);
+	sort(upd.begin(),upd.end());
+	LL pos1=0;
+	int pos2=0;
+	while(pos1<=maxv){
+		if(pos2<upd.size()){
+			if(upd[pos2].a==pos1){
+				Insert(upd[pos2],0,maxv);
+				pos1=upd[pos2++].b+1;
+			}
+			else{
+				Insert(opt{pos1,upd[pos2].a-1,m},0,maxv);
+				pos1=upd[pos2].a;
+			}
+		}
+		else{
+			Insert(opt{pos1,maxv,m},0,maxv);
+			pos1=maxv+1;
+		}
+	}
+	build(0,nodes.size()-1,0,maxv);
+	_for(i,0,nodes.size()){
+		p[i]=i;
+		mp.push_back(nodes[i].b);
+	}
+	stack<int> ans;
+	for(int i=m;i>=0;i--){
+		for(pair<int,int> pr:edges[i]){
+			int x=Find(pr.first),y=Find(pr.second);
+			if(x!=y)
+			p[x]=y;
+		}
+		if(query[i].first!=-1){
+			int p1=lower_bound(mp.begin(),mp.end(),query[i].first)-mp.begin();
+			int p2=lower_bound(mp.begin(),mp.end(),query[i].second)-mp.begin();
+			p1=Find(p1);
+			p2=Find(p2);
+			if(p1==p2)
+			ans.push(1);
+			else
+			ans.push(0);
+		}
+	}
+	while(!ans.empty()){
+		enter(ans.top());
+		ans.pop();
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具