首页 > 代码库 > 【bzoj3514】 Codechef MARCH14 GERALD07加强版
【bzoj3514】 Codechef MARCH14 GERALD07加强版
http://www.lydsy.com/JudgeOnline/problem.php?id=3514 (题目链接)
题意
给出$n$个点$m$条边的无向图，询问保留图中编号在$[l,r]$的边的时候图中的连通块的个数。
Solution
将边的编号作为权值用LCT维护一个最大生成树，同时记录一下加入当前边$i$会把哪一条原本在生成树中的边踢掉，记作$ntr[i]$。如果不会踢掉任意一条边，那么$ntr[i]=0$。如果$i$是自环，那么$ntr[i]=i$。
求出$ntr$数组有什么用呢，我们以它构建一棵主席树。对于一个询问$[l,r]$，我们想知道在这些边中有用的边有几条，那么有用的边$ntr$的前一条边的编号一定是在$l$之前的，所以我们在主席树上查询一下区间$[l,r]$中$ntr$在$[0,l-1]$中的边有几条。这样查出来的值就是有用的边的条数，每加入一条有用的边，都会时连通块个数-1，于是我们就可以统计答案了。
细节
cut的时候cut的是被ntr的边两端的节点，手一快就打错了，还查了好久T_T
代码
// bzoj3514#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define lim 1000000000#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=200010;int n,m,Q,T,ans,rt[maxn],ntr[maxn];struct edge {int u,v;}e[maxn];struct node { int son[2],s,rev; int& operator [] (int x) {return son[x];}};namespace LCT { int fa[maxn<<1]; node tr[maxn<<1]; void reverse(int x) { tr[x].rev^=1; swap(tr[x][0],tr[x][1]); } void pushup(int x) { tr[x].s=x<=n ? inf : x; int l=tr[x][0],r=tr[x][1]; if (l) tr[x].s=min(tr[x].s,tr[l].s); if (r) tr[x].s=min(tr[x].s,tr[r].s); } void pushdown(int x) { if (tr[fa[x]][0]==x || tr[fa[x]][1]==x) pushdown(fa[x]); if (tr[x].rev) { if (tr[x][0]) reverse(tr[x][0]); if (tr[x][1]) reverse(tr[x][1]); tr[x].rev^=1; } } void rotate(int x) { int y=fa[x],z=fa[y],l,r; l=tr[y][1]==x;r=l^1; if (tr[z][0]==y || tr[z][1]==y) tr[z][tr[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[tr[x][r]]=y; tr[y][l]=tr[x][r];tr[x][r]=y; pushup(y);pushup(x); } void splay(int x) { pushdown(x); while (tr[fa[x]][0]==x || tr[fa[x]][1]==x) { int y=fa[x],z=fa[y]; if (tr[z][0]==y || tr[z][1]==y) { if (tr[z][0]==y ^ tr[y][0]==x) rotate(x); else rotate(y); } rotate(x); } } void access(int x) { for (int y=0;x;y=x,x=fa[x]) splay(x),tr[x][1]=y,pushup(x); } void makeroot(int x) { access(x);splay(x);reverse(x); } int query(int x,int y) { makeroot(x);access(y);splay(y);return tr[y].s; } void link(int x,int y) { makeroot(x);fa[x]=y; } void cut(int x,int y) { makeroot(x);access(y);splay(y); fa[x]=tr[y][0]=0;pushup(y); } int find(int x) { return fa[x] ? find(fa[x]) : x; } void main() { for (int i=1;i<=m;i++) { scanf("%d%d",&e[i].u,&e[i].v); if (e[i].u==e[i].v) ntr[i]=i; else if (find(e[i].u)==find(e[i].v)) { int x=query(e[i].u,e[i].v); ntr[i]=x-n; cut(x,e[x-n].u); cut(x,e[x-n].v); link(i+n,e[i].u);link(i+n,e[i].v); } else ntr[i]=0,link(i+n,e[i].u),link(i+n,e[i].v); } }}namespace Chairtree { int sz; node tr[maxn*40]; void build(int &u,int v,int l,int r,int val) { if (!u) u=++sz; if (l==r) {tr[u].s=tr[v].s+1;return;} int mid=(l+r)>>1; if (val<=mid) build(tr[u][0],tr[v][0],l,mid,val),tr[u][1]=tr[v][1]; else build(tr[u][1],tr[v][1],mid+1,r,val),tr[u][0]=tr[v][0]; tr[u].s=tr[tr[u][0]].s+tr[tr[u][1]].s; } int query(int u,int v,int l,int r,int ql,int qr) { if (!u && !v) return 0; if (l==ql && r==qr) return tr[v].s-tr[u].s; int mid=(l+r)>>1; if (qr<=mid) return query(tr[u][0],tr[v][0],l,mid,ql,qr); else if (ql>mid) return query(tr[u][1],tr[v][1],mid+1,r,ql,qr); else return query(tr[u][0],tr[v][0],l,mid,ql,mid)+query(tr[u][1],tr[v][1],mid+1,r,mid+1,qr); }}using namespace Chairtree;int main() { scanf("%d%d%d%d",&n,&m,&Q,&T); LCT::main(); for (int i=1;i<=m;i++) build(rt[i],rt[i-1],0,m,ntr[i]); for (int l,r,i=1;i<=Q;i++) { scanf("%d%d",&l,&r); if (T) l^=ans,r^=ans; ans=n-query(rt[l-1],rt[r],0,m,0,l-1); printf("%d\n",ans); } return 0;}
【bzoj3514】 Codechef MARCH14 GERALD07加强版
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。