BZOJ 1018: [SHOI2008]堵塞的交通traffic(线段树分治+并查集)

解题思路

　　可以离线，然后确定每个边的出现时间，算这个排序即可。然后就可以线段树分治了，连通性用并查集维护，因为要撤销，所以要按秩合并，时间复杂度\(O(nlog^2 n)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int N=100005;

inline int rd(){

	int x=0; char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x;

}

int n,tot,ans[N],fa[N<<1],siz[N<<1],num,cnt;

struct Data{

	int x,y,op,id;

	friend bool operator<(const Data A,const Data B){

		if(A.x==B.x && A.y==B.y) return A.id<B.id;

		if(A.x==B.x) return A.y<B.y;

		return A.x<B.x;

	}

}tmp[N],ask[N];

struct Node{

	int x,y,t;

	Node(int _x=0,int _y=0,int _t=0){

		x=_x; y=_y;	t=_t;

	}

};

inline int id(int x,int y){

	return (x-1)*n+y;

}

inline int get(int x){

	while(x!=fa[x]) x=fa[x];

	return x;

}

struct Segment_Tree{

	vector<Node> v[N<<2];

	vector<Node> Ask[N];

	void update(int x,int l,int r,int L,int R,Node now){

		if(L<=l && r<=R){

			if(now.t) Ask[l].push_back(now);

			else v[x].push_back(now);

			return ;

		}

		int mid=(l+r)>>1;

		if(L<=mid) update(x<<1,l,mid,L,R,now);

		if(mid<R) update(x<<1|1,mid+1,r,L,R,now);

	}

	void query(int x,int l,int r){

		int xx,yy,uu,vv; vector<Node> now;

		for(int i=0;i<v[x].size();i++){

			xx=v[x][i].x; yy=v[x][i].y;

			uu=get(xx); vv=get(yy);

			if(uu==vv) continue;

			if(siz[uu]<siz[vv]) swap(uu,vv);

			siz[uu]+=siz[vv]; fa[vv]=uu;

			now.push_back(Node(uu,vv,0));

		}

		int mid=(l+r)>>1;

		if(l==r){

			for(int i=0;i<Ask[l].size();i++) {

				xx=get(Ask[l][i].x); yy=get(Ask[l][i].y);

				ans[Ask[l][i].t]=(xx==yy)?1:0;

			}

		}

		else query(x<<1,l,mid),query(x<<1|1,mid+1,r);

		for(int i=0;i<now.size();i++){

			xx=now[i].x; yy=now[i].y;

			fa[yy]=yy; siz[xx]-=siz[yy];

		}

	}

}tree;

int main(){

	n=rd(); int x1,y1,x2,y2,id1,id2; char s[10];

	for(int i=1;i<=n*2;i++) fa[i]=i,siz[i]=1;

	while(1){

		scanf("%s",s+1);

		if(s[1]=='E') break; cnt++;

		x1=rd(),y1=rd(),x2=rd(),y2=rd();

		id1=id(x1,y1); id2=id(x2,y2);

		if(id1>id2) swap(id1,id2);

		if(s[1]=='A') {

			num++; ask[num].id=cnt;

			ask[num].x=id1; ask[num].y=id2;

			continue;

		}

		tot++; tmp[tot].id=cnt;

		tmp[tot].x=id1; tmp[tot].y=id2;

		if(s[1]=='O') tmp[tot].op=0;

		else tmp[tot].op=1;

	}

	sort(tmp+1,tmp+1+tot);

	for(int i=1;i<=num;i++)

		tree.update(1,1,cnt,ask[i].id,ask[i].id,Node(ask[i].x,ask[i].y,i));

	for(int i=1;i<=tot;i++){

		if(tmp[i].op==0 && tmp[i+1].x==tmp[i].x && tmp[i+1].y==tmp[i].y)

			tree.update(1,1,cnt,tmp[i].id,tmp[i+1].id,Node(tmp[i].x,tmp[i].y,0)),++i;

		else tree.update(1,1,cnt,tmp[i].id,cnt,Node(tmp[i].x,tmp[i].y,0));

	}

	tree.query(1,1,cnt);

	for(int i=1;i<=num;i++)

		puts(ans[i]?"Y":"N");

	return 0;

}

巴特西

BZOJ 1018: [SHOI2008]堵塞的交通traffic(线段树分治+并查集)

解题思路

代码

最新文章

热门文章