[SHOI2008]堵塞的交通traffic
题意:
题解:
听说这题正解是线段树,然而我这个蒟蒻并看不懂线段树的做法,然后看见这题的讨论区里提到了一个叫分治并查集的东西,于是我就学了一发这个奇妙的东西并A了这道题.
分治并查集可以用来离线维护一张图的连通性.首先,我们需要离线,把所有询问读进来,对于每条边,它出现的时间肯定是几段区间,于是可以按照时间建一棵线段树,线段树的每个节点存的是在该节点的时间区间内一直存在的边.建完线段树后我们对这棵线段树进行dfs,每次进入该节点就将该节点的所有边都加上,然后离开该节点就将该节点的所有边删除.这样,我们的删除操作就变成了撤销操作,即我们需要一棵支持合并和撤销的并查集.对于这种并查集,我们不能路径压缩,而是需要启发式合并(将size小的节点并到size大的上).这样我们发现每次合并只会更改2个节点的信息.于是我们就可以把更改前这2个节点的信息存下来,然后撤销的时候赋回原来的值就行了.
这样这道题就是维护形状比较特殊的图的连通性了.
代码中对于线段树的每个节点存了一个前向星表示该节点包含的边,并且对于并查集用了一个小更改:对于集合的根节点,它的fa是它的size的相反数,否则它的fa就是它的父节点.
#include<cstdio> #include<map> using namespace std; const int N=100000,lgN=19; struct query{int op,l,r;}a[N+10]; int ask_id[N+10],ask_cnt,n,m; int hsh(int x,int y){return (x-1)*n+y;} int query_id[N*lgN+10],nxt[N*lgN+10],qcnt; struct node{int l,r,h;}b[N*4+10]; void build_tree(int p,int l,int r){ b[p].l=l; b[p].r=r; if(l!=r){ int mid=(l+r)/2; build_tree(p*2,l,mid); build_tree(p*2+1,mid+1,r); } } void add(int p,int l,int r,int v){ if(b[p].l==l&&b[p].r==r){ query_id[++qcnt]=v; nxt[qcnt]=b[p].h; b[p].h=qcnt; return; } int mid=(b[p].l+b[p].r)/2; if(r<=mid) add(p*2,l,r,v); else if(l>mid) add(p*2+1,l,r,v); else{ add(p*2,l,mid,v); add(p*2+1,mid+1,r,v); } } map<pair<int,int>,int> M,MM; int fa[N*2+10],record[N*lgN+10][4],rec_cnt; int getf(int x){for(;fa[x]>0;x=fa[x]); return x;} void dfs_ans(int p){ int nowl=rec_cnt+1; for(int i=b[p].h;i;i=nxt[i]){ int l=getf(a[query_id[i]].l),r=getf(a[query_id[i]].r); if(l==r) continue; if(fa[l]>fa[r]) swap(l,r); record[++rec_cnt][0]=l; record[rec_cnt][1]=fa[l]; record[rec_cnt][2]=r; record[rec_cnt][3]=fa[r]; fa[l]+=fa[r]; fa[r]=l; } if(b[p].l==b[p].r) printf("%s\n",getf(a[ask_id[b[p].l]].l)==getf(a[ask_id[b[p].l]].r)?"Y":"N"); else{ dfs_ans(p*2); dfs_ans(p*2+1); } for(;rec_cnt>=nowl;--rec_cnt){ fa[record[rec_cnt][0]]=record[rec_cnt][1]; fa[record[rec_cnt][2]]=record[rec_cnt][3]; } } int main(){ scanf("%d",&n); for(int i=1;i<=n*2;++i) fa[i]=-1; for(;;){ char s[2]; int r1,c1,r2,c2; scanf("%s",s); if(s[0]=='E') break; ++m; scanf("%d%d%d%d",&r1,&c1,&r2,&c2); if(s[0]=='O') a[m].op=0; else if(s[0]=='C') a[m].op=1; else if(s[0]=='A'){ a[m].op=2; ask_id[++ask_cnt]=m; } a[m].l=hsh(r1,c1); a[m].r=hsh(r2,c2); if(a[m].l>a[m].r) swap(a[m].l,a[m].r); } if(ask_cnt==0) return 0; build_tree(1,1,ask_cnt); for(int i=1,j=1;i<=m;++i){ pair<int,int> P=make_pair(a[i].l,a[i].r); if(a[i].op==0){ if(!M[P]){ M[P]=j; MM[P]=i; } }else if(a[i].op==1){ if(M[P]){ if(M[P]<=j-1) add(1,M[P],j-1,i); M[P]=0; } }else ++j; } for(map<pair<int,int>,int>::iterator it=M.begin();it!=M.end();++it) if(it->second&&it->second<=ask_cnt) add(1,it->second,ask_cnt,MM[it->first]); dfs_ans(1); return 0; }